2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$
2
$\begingroup$

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.
$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.