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?
 A: 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.

A: 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}$$
A: 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.
