# How many binary strings of length $n$ with no two adjacent 1's and four more 0's than 1's?

I want to count the number of binary strings which meet the following three conditions:

• The number of $0$s is exactly four more than the number of $1$s.
• There are no two adjacent $1$s.
• The string does not start and end with a $1$. So, for instance, $001001001001$ is acceptable, but $10000001$ isn't.

How many strings of length $n$ meet those conditions?

HINT: Suppose that there are $k$ ones. Then there are $k+4$ zeroes, so $n=2k+4$. In particular, $n$ must be even, so if $a_n$ is the number of acceptable strings of length $n$, then $a_n=0$ when $n$ is odd. Now it’s just a matter of counting the ways to place $k$ ones in a string of length $2k+4$ in such a way that no two of them are adjacent, and at least one of the end characters is a zero.

Think of the ones as dividers; your task is to distribute the $k+4$ zeroes in the $k+1$ spaces before, between, and after the ones in such a way that each of the $k-1$ internal spaces gets at least one zero, and at least one of the end spaces gets a zero. This is a slight variation of a standard stars and bars problem.

• First determine how many ways there are to distribute the $k+4$ zeroes so that each of the $k+1$ spaces except the last gets at least one of them.
• Then determine how many ways there are to distribute the $k+4$ zeroes so that each of the $k+1$ spaces except the first gets at least one of them.
• Then determine how many ways there are to distribute the zeroes amongst the $k-1$ internal spaces so that each of these spaces gets at least one of them.
• Then combine these results appropriately.

Let $S_{n,t}$ be the number of strings of length $n$ that have exactly $t$ more $0s$ than $1s$, with no two consecutive $1s$, and end with $0$. Then, each $1$ will have a companion $0$ at its right. We have $p$ such "$10$" pairs, with $2 p +t = n$ (this implies $n-t$ must be even).

Then $S_{n,t}$ counts all the possible arrangements of these pseudo $p+t$ elements ($p$ $01$ pairs and $t$ $0$s), which is $$S_{n,t}={p+t \choose t}={\frac{1}{2}(n+t) \choose t}$$

We are left with the strings that, again, have exactly $t$ more $0s$ than $1s$, no two consecutive $1s$, but now end with $1$ (hence they must start with $0$). Considering the effect of removing these extreme elements, the shortened string fullfills the condition of the previous case, so the counting is $S_{n-2,t}$

Then the total number is

$$S_{n,t}+S_{n-2,t}={\frac{1}{2}(n+t) \choose t}+{\frac{1}{2}(n+t)-1 \choose t} ={\frac{1}{2}(n+t) \choose t} \frac{2\,n}{n+t}$$

Suppose we seek to count binary string of length $n$ that meet these conditions:

• The number of zeros is $t$ more than the number of ones.
• There are no two adjacent ones.
• The string does not start and end in one.

Use $z$ to represent the zeros and $w$ to represent the ones.

We have for the case of the string that starts and ends in zero the generating function

$$G(z,w) = \frac{z}{1-z} \sum_{k\ge 0} \left(w \frac{z}{1-z}\right)^k = \frac{z}{1-z} \frac{1}{1-wz/(1-z)} \\ = \frac{z}{1-z-wz}.$$

There are two more possibilities corresponding to a leading or trailing one but not both. This gives

$$H(z,w) = G(z,w) + wG(z,w) + G(z,w)w = \frac{z}{1-z-wz} (1+2w).$$

Now observe that

$$[z^n] F(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} F(z) \; dz$$

so that we get for the cofficient $[z^{q+t} w^q] H(z,w)$ (the initial representation of $G(z,w)$ is more useful here)

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{q+t+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{q+1}} \frac{z}{1-z-wz} (1+2w) \; dw\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{1-z} \frac{1}{z^{q+t+1}} \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{q+1}} \frac{z}{1-wz/(1-z)} (1+2w) \; dw\; dz.$$

Extracting coefficients in $w$ yields

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{1-z} \frac{1}{z^{q+t+1}} \left(\frac{z^{q+1}}{(1-z)^q} + 2 \frac{z^{q}}{(1-z)^{q-1}} \right) \; dz.$$

This has two pieces call them $X_1$ and $X_2.$ We obtain for $X_1$

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1-z)^{q+1}} \frac{1}{z^{t}} \; dz = {t-1+q\choose q}$$

and for $X_2$

$$2\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1-z)^q} \frac{1}{z^{t+1}} \; dz = 2{t+q-1\choose q-1}.$$

Collecting $X_1$ and $X_2$ yields

$$\frac{t}{q} {t+q-1\choose q-1} + 2 {t+q-1\choose q-1} = \frac{2q+t}{q} {t+q-1\choose q-1}.$$

Given that $2q+t=n$ we can re-write this as $$\frac{n}{(n-t)/2} {t+(n-t)/2-1\choose t} = \frac{2n}{n-t} {(n+t)/2-1\choose t}.$$

Further re-arrangeing yields

$$\frac{2n}{n-t} \frac{(n-t)/2}{(n+t)/2} {(n+t)/2\choose t} = \frac{2n}{n+t} {(n+t)/2\choose t}.$$

Remark. Admittedly we don't need complex variables here, we can just use the Newton binomial. E.g.

$$[w^q] \frac{z}{1-z-wz} = \frac{1}{1-z} [w^q] \frac{z}{1-wz/(1-z)} = \frac{1}{1-z} \frac{z^{q+1}}{(1-z)^q}$$

and so on.