Counting permutations of binary string where all ones within some distance? Given a binary string consisting of $O$ ones and $Z$ zeros, I'd like to count the number of permutations of that string where all of the ones are within a window (consecutive positions) of length $L$.
For example, with 5 ones and 6 zeros, there are 81 permutations where the ones are all within $l=7$ consecutive positions (I did this enumerating and counting them).
I think that using inclusion-exclusion is the way to solve this, but to be honest I understand the gist of the technique but usually struggle to understand what to count and how to count them to get the alternating I-E terms.
I tried to adapt an answer from an earlier question here - it is quite similar, except instead of a straight partitioning of a permutation, it's partitioning with offsets of only 1 per partition, but to no avail.
This seems like it should be quite simple, I'd appreciate some frustration relief.

Generally for these kind of counting problems you must build a recursion to handle the valid sequences. And after from the recursion you can build it generating function.
But this will not be needed for this simple count.
Let $a$ the number of ones, $b$ the number of zeros and $\ell$ the length. From the length and the number of ones you must build "simple distinguishable blocks", in this case by example blocks that start and end with a one, of length less or equal to $\ell$, that contain all the ones.
Then fix an one in the first and last position and count all the possible permutations for the $a-2$ remaining ones in the $r-2$ remaining positions, where $a-2\le r-2\le \ell-2$, i.e. $a\le r\le \ell$ are all the valid length where you can put the $a$ ones inside.
Then for each $r\in\{a,a+1,...,\ell\}$ you will had $\binom{r-2}{a-2}$ different permutations of a string of length $r$ with a one in the first and last position.
And then for each $r$ you have different permutations depending in the number of the remaining zeros in the left or the right of the string, in particular for any $r$ you will had $b-(r-2-a+2)+1=b-r+a+1$ possible permutations.
Then the final answer is
$$\sum_{r=a}^\ell \binom{r-2}{a-2}(b+a+1-r)$$
This formula have a closest form... but Im too lazy to write it now, sorry. You can check it in wolframalpha.
P.S.: this seem the same answer that put Brian but with a different wording :P

Fighting my laziness I will add a beautiful way to get the closed form of the above sum using finite calculus:
Summation by parts:
$$\sum f\Delta g=fg-\sum {\rm E}g\Delta f$$
where 
$$\Delta f(k)=f(k+1)-f(k)\quad\text{and}\quad{\rm E}f(k)=f(k+1)$$
Finite integral example and notation:
$$\sum_{k=r}^sf(k)=\sum\nolimits_r^{s+1}f(k)\delta k=\sum\nolimits_r^{s+1}f(k)\delta (k+c)$$
$$\sum\binom{k+a}{k}\delta k=\binom{k+a}{k-1}+C$$
Our case:
By summation by parts let $\Delta_r f(r)=\binom{r-2}{a-2}$ and $g(r)=(a+b-r+1)$. Then using the above formulas we get
$$\sum (a+b+1-r)\binom{r-2}{a-2}\delta r=(a+b-r+1)\binom{r-2}{r-a-1}+\sum\binom{r-1}{r-a}\delta r\\=(a+b-r+1)\binom{r-2}{r-a-1}+\binom{r-1}{r-a-1}+C$$
And then taking limits we finally get:
$$\sum_{r=a}^\ell \binom{r-2}{a-2}(b+a+1-r)=\left((a+b-r+1)\binom{r-2}{r-a-1}+\binom{r-1}{r-a-1}+C\right)\Bigg|_a^{\ell+1}=\\\color{red}{\boxed{=(a+b-\ell)\binom{\ell-1}{\ell-a}+\binom{\ell}{\ell-a}}}$$
P.S.: check it!
