Counting permutations of binary string where all ones within some distance?

Question

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.

Answer 1

You don’t need an inclusion-exclusion argument. Let me use $n_0$ and $n_1$ for the numbers of zeroes and ones, respectively, and let $n=n_0+n_1$. Let $\ell$ be the length of the window; I’ll assume that $n_1\le\ell\le n$.

For $n_1\le k\le\ell$ we can count the number of strings in which the actual window occupied by the ones has length $k$. If the first $1$ is at position $i$, the last is at position $i+k-1$. We must have $i+k-1\le n$, so $1\le i\le n+1-k$, meaning that there are $n+1-k$ possible starting points for the ones. There are $k-2$ positions between the first and last ones, and $n_1-2$ of them must be occupied by ones, so there are $\binom{k-2}{n_1-2}$ ways to place the interior ones. Thus, there are

$$(n+1-k)\binom{k-2}{n_1-k}$$

strings in which the actual window occupied by the ones has length $k$, and there are altogether

$$\sum_{k=n_1}^\ell(n+1-k)\binom{k-2}{n_1-2}$$

acceptable strings.

With your example of $n_0=6,n_1=5$, and $\ell=7$ this becomes $$7\binom33+6\binom43+5\binom53=7+24+50=81\;.$$

Finally,

$$\begin{align*} \sum_{k=n_1}^\ell(n+1-k)\binom{k-2}{n_1-2}&=n\sum_{k=n_1}^\ell\binom{k-2}{n_1-2}-\sum_{k=n_1}^\ell(k-1)\binom{k-2}{n_1-2}\\ &=n\sum_{k=n_1-2}^{\ell-2}\binom{k}{n_1-2}-\sum_{k=n_1-2}^{\ell-2}(k+1)\binom{k}{n_1-2}\\ &=n\binom{\ell-1}{n_1-1}-(n_1-1)\sum_{k=n_1-2}^{\ell-2}\binom{k+1}{n_1-1}\\ &=n\binom{\ell-1}{n_1-1}-(n_1-1)\sum_{k=n_1-1}^{\ell-1}\binom{k}{n_1-1}\\ &=n\binom{\ell-1}{n_1-1}-(n_1-1)\binom{\ell}{n_1}\;.\tag{1} \end{align*}$$

In your example this is $$11\binom64-4\binom75=165-84=81\;.$$

The expression $(1)$ can be manipulated in various ways; for instance,

$$\begin{align*} n\binom{\ell-1}{n_1-1}-(n_1-1)\binom{\ell}{n_1}&=n\binom{\ell-1}{n_1-1}-(n_1-1)\left(\binom{\ell-1}{n_1-1}+\binom{\ell-1}{n_1}\right)\\ &=(n_0+1)\binom{\ell-1}{n_1-1}-(n_1-1)\binom{\ell-1}{n_1}\;. \end{align*}$$

Answer 2

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!