Counting binary words by runs

88 Views Asked by At

I would like to count the number of binary words that have $m$ zeros, $n$ ones and $k$ runs of ones (consecutive blocks of ones). Call it $a(m,n,k)$. I tried to apply the symbolic method and introduced the class $\cal{A} = \{\text{ binary words } \}$ and the generating function

$$A(x,y,z) = \sum_{\alpha \in\cal{A}} x^{|\alpha|_0}y^{|\alpha|_1}z^{|\alpha|_r}$$

where $|\alpha|_k$ is the number of digits $k=0,1$ in $\alpha$ and $|\alpha|_r$ is the number of runs of ones.

Now I think the following holds (since a word either has some amount of ones as the first run (with some amount of zeros in front), or it has no ones)

$$\cal{A} = \left( \bigcup_{j=0}^\infty \bigcup_{m=1}^\infty \{ \underbrace{0\dots0}_j \underbrace{1\dots 1}_m0 \} \times \cal{A} \right ) \bigcup \{\varepsilon, 0, 00, 000, \dots\}$$

And from this we get an equation for the generating function:

$$A = \left(\sum_{j=0}^\infty \sum_{m=1}^\infty x^{j+1}y^mzA\right) + 1+x+x^2+\dots \\= \frac{x}{1-x} \frac{y}{1-y}z A + \frac{1}{1-x} $$ And hence $$ \\A= \frac{1}{1-x} \frac{1}{1- \frac{xy}{(1-x)(1-y)}z} \\= \frac{1}{1-x} \sum_{k=0}^\infty \left(\frac{xy}{(1-x)(1-y)}\right)^kz^k \\= \sum_{k=0}^\infty x^ky^k (1-x)^{-k-1} (1-y)^{-k} z^k \\= \sum_{m\geq 0} \sum_{n\geq 0} \sum_{k\geq 0} (-1)^{m+n}{{-k-1}\choose{m}}{{-k}\choose{n}} x^{m+k}y^{n+k}z^k \\= \sum_{m\geq k} \sum_{n\geq k} \sum_{k\geq 0} (-1)^{m+n}{{-k-1}\choose{m-k}}{{-k}\choose{n-k}} x^{m}y^{n}z^k $$

From here we see the solution

$$a(m,n,k) = (-1)^{m+n}{{-k-1}\choose{m-k}}{{-k}\choose{n-k}} \\= {{m}\choose{k}}{{n}\choose{k-1}} $$

But I think this is incorrect, since for example for $m=0$ you should always have $1$ run, but in my result the first factor will make it $0$. Where is my error? My source for the problem is this homework question 2 and there are also solutions on the page, but I would like to solve it myself.

1

There are 1 best solutions below

0
On BEST ANSWER

As I mentioned in a comment, you are not counting strings which end with a $1$. That is, letting $\mathcal B=\{\text{binary words ending in 0}\}\cup\{\epsilon\}$, and letting $B(x,y,z)=\sum_{\beta\in \mathcal B}x^{|\beta|_0}y^{|\beta|_1}z^{|\beta|_r}$, you have shown that $$ B(x,y,z)= \sum_{m\geq k} \sum_{n\geq k} \sum_{k\geq 0} {{m}\choose{k}}{{n-1}\choose{k-1}} x^{m}y^{n}z^k $$ However, there is a quick fix. You can note that $$ xA(x,y,z)+1=B(x,y,z) $$ corresponding the to the equation $\mathcal B=(\mathcal A\times \{0\})\cup \{\epsilon\}$. This gives you

$$ A(x,y,z)= \sum_{m\geq k} \sum_{n\geq k} \sum_{k\geq 0} {{m}\choose{k}}{{n-1}\choose{k-1}} x^{m-1}y^{n}z^k $$ Extracting the $[x^my^nz^k]$ coefficient, you get $\binom{m+1}{k}\binom{n-1}{k-1}$.


Here is a different method which works; let

$\mathcal M=\{\text{binary words beginning with a }0\}\cup \{\epsilon\}$,
$\mathcal N=\{\text{binary words beginning with a }1\}$.

Then you get the mutual recurrence $$ \begin{align} \mathcal M &= \left(\bigcup_{i\ge1}0^i× \mathcal N\right)\cup \{\epsilon,0,00,\dots\},\\ \mathcal N &= \left(\bigcup_{i\ge1}1^i× \mathcal M\right) \end{align} $$ which, letting $M$ and $N$ be the corresponding generating functions, implies $$ \begin{align} M&=\frac{x}{1-x}N + \frac1{1-x}\\ N&=\frac{yz}{1-y}M \end{align} $$ You can then solve this system for $M$ and $N$. Conclude by noting $A=M+N$.