A formula for bit strings with no $k$ consecutive $1$'s using generating functions

Question

The following problem is taken from the book generatingfunctionology (P.28) by Herbert S. Wilf.

Let $f(n,m,k)$ be the number of strings of $n$ $\,0$'s and $1$'s that contain exactly $m\,$ $1$'s, no $k$ of which are consecutive.

(a) Find a recurrence formula for $f$. It should have $f(n,m,k)$ on the left side, and exactly three terms on the right.

(b) Find, in simple closed form, the generating functions $$ F_k(x,y)=\sum_{n,m\ge0}f(n,m,k)x^ny^m \,\,\,\,\,\,\,\,\ (k=1,2,...). $$ (c) Find an explicit formula for $f(n,m,k)$ from the genrating function (this should involve only a single summation, of an expression that involves a few factorials).

I was able to solve (a) and (b) and found that the generating functions is $$ F_k = \frac{1-x^ky^k}{1-x-xy-x^{k+1}y^k} $$ However, I cannot seem to be able to extract the sequence from this function. Any help will be appreciated.

---

Edit:

I've added the way I solved (a) and (b) to allow any criticism in case I got the function wrong. My solution to (a) goes as follows:

Given $m,n,k$ such that $0\le k\le m \le n$ and $k\lt n$, we look at all of the bit string of length $n$ that contain exactly $m$ $1$'s, no $k$ of which are consecutive. We split these strings into two sets. The first composed of all the strings that end with $0$. This set has $f(n-1,m, k)$ strings since by removing the $0$ from the end of the string we obtain a one to one correspondence between the strings in our set and the strings $f(n-1,m, k)$ counts. The other set is composed of all the strings that end with $1$. By removing the last bit we obtain a one to one correspondence between our set and all strings counted by $f(n-1,m-1, k)$, except those that have $k-1$ consecutive $1$'s at the end. To count the latter we first note that since $k\lt n$ there must be another bit, which must be $0$, before the last $k-1$ $\,1$'s. By removing the last $k$ bits ($10\cdots0$) we obtain a one to one correspondence with the strings that are counted by $f(n-k-1,\,m-k,\,k)$. With that we obtain the recursion: $$f(n,m,k) = f(n-1,m,k) + f(n-1,m-1,k) - f(n-k-1,\,m-k,\,k)$$ In addition, we note the if $0\le m \le n$ and $k > m$, then $f(n,m,k) = \binom{n}m$ , since we can't have more consecutive $1$'s than there are $1$'s, so the problem is reduced to counting the number of strings with length $n$ that have $m$ $1$'s. For all other cases we write $f(n,m,k) = 0$ which completes the definition.

To Solve (b) I did the following:

$$ \begin{align} F_k(x,y) & = \sum_{n,m\ge0}f(n,m,k) x^n y^m \\ & = \sum_{n=0}^{\infty}\sum_{m=0}^{n}f(n,m,k) x^n y^m \\ & = \sum_{n=0}^{k-1}\sum_{m=0}^{n}f(n,m,k) x^n y^m + \sum_{n=k}^{\infty}\sum_{m=0}^{k-1}f(n,m,k) x^n y^m + \sum_{n=k}^{\infty}\sum_{m=k}^{n}f(n,m,k) x^n y^m \\ & = \sum_{n=0}^{k-1}\sum_{m=0}^{n}\binom{n}m x^n y^m + \sum_{n=k}^{\infty}\sum_{m=0}^{k-1}\binom{n}m x^n y^m + \sum_{n=k}^{\infty}\sum_{m=k}^{n}f(n,m,k) x^n y^m \end{align} $$ By using the convention that $\binom{n}m = 0$ when $m\gt n$, and noting that when $m=n\ge k$ we have $f(n,m,k)=0$ we can write the above equation as follows: $$ \begin{align} & \sum_{m=0}^{k-1}\sum_{n=0}^{\infty}\binom{n}m x^n y^m + \sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n,m,k) x^n y^m \\ =& \sum_{m=0}^{k-1} \frac{x^m}{(1-x)^{m+1}} y^m + \sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n,m,k) x^n y^m \\ =& \frac{1}{1-x} \cdot \omega(x,y) + \sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n,m,k) x^n y^m \end{align} $$ where: $$\omega(x,y) := \frac{1 - (\frac{xy}{1-x})^k}{1 - \frac{xy}{1-x}}.$$ Using the recusion formula obtained in (a) we can expand the second summand like so: $$ \begin{align} \sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n,m,k) x^n y^m & = A + B - C \end{align} $$ where: $$ \begin{align} A & =\sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n-1,m,k) x^n y^m \\ & = x\sum_{n=k}^{\infty}\sum_{m=k}^{n}f(n,m,k) x^n y^m \\ & = x\left(\sum_{n=0}^{\infty}\sum_{m=0}^{n}f(n,m,k) x^n y^m - \sum_{n=0}^{k-1}\sum_{m=0}^{n}f(n,m,k) x^n y^m - \sum_{n=k}^{\infty}\sum_{m=0}^{k-1}f(n,m,k) x^n y^m \right)\\ & = x\left(F_k(x,y) - \sum_{n=0}^{k-1}\sum_{m=0}^{n}\binom{n}m x^n y^m - \sum_{n=k}^{\infty}\sum_{m=0}^{k-1}\binom{n}m x^n y^m \right)\\ & = x\left(F_k(x,y) - \sum_{m=0}^{k-1}\sum_{n=0}^{\infty}\binom{n}m x^n y^m\right)\\ & = xF_k(x,y) - \frac{x}{1-x} \cdot \omega(x,y)\\ \\ B & =\sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n-1,m-1,k) x^n y^m \\ & = xy\sum_{n=k}^{\infty}\sum_{m=k-1}^{n-1}f(n,m,k) x^n y^m \\ & = xy\left(\sum_{n=0}^{\infty}\sum_{m=0}^{n}f(n,m,k) x^n y^m - \sum_{n=0}^{k-1}\sum_{m=0}^{n}f(n,m,k) x^n y^m - \sum_{n=k}^{\infty}\sum_{m=0}^{k-2}f(n,m,k) x^n y^m \right)\\ & = xy\left(F_k(x,y) - \sum_{n=0}^{k-1}\sum_{m=0}^{n}\binom{n}m x^n y^m - \sum_{n=k}^{\infty}\sum_{m=0}^{k-2}\binom{n}m x^n y^m \right)\\ & = xy\left(F_k(x,y) - \sum_{m=0}^{k-2}\sum_{n=0}^{\infty}\binom{n}m x^n y^m - x^{k-1}y^{k-1}\right)\\ & = xyF_k(x,y) - xy\sum_{m=0}^{k-2}\sum_{n=0}^{\infty}\binom{n}m x^n y^m - x^ky^k\\ & = xyF_k(x,y) - xy\sum_{m=0}^{k-2}\frac{x^m}{(1-x)^{m+1}} y^m - x^ky^k\\ & = xyF_k(x,y) + 1 - \omega(x,y) - x^ky^k\\ \\ C & =\sum_{n=k+1}^{\infty}\sum_{m=k}^{n-1}f(n-k-1,\,m-k,\,k) x^n y^m = x^{k+1}y^kF_k(x,y) \end{align} $$ Summing all the values we get: $$ F_k = \frac{1}{1-x} \cdot \omega + xF_k - \frac{x}{1-x} \cdot \omega + xyF_k + 1 - \omega - x^ky^k - x^{k+1}y^kF_k $$ And so (note that $\omega$ disappears): $$ F_k = \frac{1-x^ky^k}{1-x-xy-x^{k+1}y^k} $$

Answer 1

First of all, some unsolicited advice: your derivation for (b) need not be so messy. It greatly simplifies things to observe that $$ f(n,m,k) = f(n-1,m,k) + f(n-1,m-1,k) - f(n-k-1,m-k,k) \tag{1} $$ holds not just when $0 \le k \le m \le n$, $k < n$. In fact, it holds for any $n \ge 0, m \ge 0, k \ge 1$, except in the two cases $m = n = k$, and $m = n = 0$. This of courses assumes that $f(n,m,k) = 0$ if $n < 0$ or $m < 0$. Proof:

• If $m > n$, then the LHS and RHS of (1) are both zero, so the equation holds.

• If $m \le n$ and $k > m$, then the LHS is ${n \choose m}$, while the RHS is ${n-1 \choose m} + {n-1 \choose m-1} + 0$, so (1) holds, unless $n = 0$ in which case we have the first exception $m = n = 0$.

• If $m \le n$ and $k \le m$ and $k < n$, then (1) holds by the counting argument you gave.

• If $m \le n$ and $k \le m$ and $k \ge n$, i.e. $k = m = n$, then the LHS is $0$ while the RHS is $0 + 1 - 0 = 1$, so we have the second exception.

This covers all cases. So then you can just write \begin{align*} F_k(x,y) & = \sum_{n,m\ge0}f(n,m,k) x^n y^m \\ & = 1 - x^k y^k \\ &\quad + \sum_{n,m\ge0} \big[ f(n-1,m,k) + f(n-1,m-1,k) - f(n-k-1, m-k,k) \big] x^n y^m \\ &= 1 - x^k y^k + (x + xy - x^{k+1} y^k) F_k(x,y) \\ F_k(x,y) &= \frac{1 - x^k y^k}{1 - x - xy + x^{k+1}{y^k}}. \end{align*}

Then you avoid all the gross introduction of $\omega$, etc. ;)

For part (c)

Write as follows:

\begin{align*} F_k(x,y) &= \frac{1 - x^k y^k}{1 - x - xy + x^{k+1}{y^k}} \\ &= \frac{1 - x^k y^k}{1 - xy - x(1 - x^ky^k)} \\ &= \frac{1}{x} \left( \frac{x(1 - x^k y^k)}{1 - xy - x(1 - x^ky^k)} \right) \\ &= \frac{1}{x} \left( \frac{1 - xy - \left[1 - xy - x(1 - x^k y^k)\right]}{1 - xy - x(1 - x^ky^k)} \right) \\ &= \frac{1}{x} \left( \frac{1 - xy}{1 - xy - x(1 - x^ky^k)} - 1 \right) \\ &= \frac{1}{x} \left( \frac{1}{1 - x(1 + xy + x^2y^2 + \cdots + x^{k-1}y^{k-1})} - 1 \right) \\ \end{align*}

Now, \begin{align*} &\; \frac{1}{1 - x(1 + xy + x^2y^2 + \cdots + x^{k-1}y^{k-1})} \\ &= \sum_{N \ge 0} x^N \left(1 + xy + x^2y^2 + \cdots + x^{k-1}y^{k-1}\right)^N \\ \end{align*}

We want the coefficient of $x^{n+1}y^m$ in this series (because then this will multiply by $\frac{1}{x}$ to give us the coefficient of $x^n y^m$, $f(n,m,k)$.) For the coefficient of $x^{n+1} y^m$, we need $N = n + 1 -m$. So we want the coefficient of $x^m y^m$ in $$ \left(1 + xy + x^2y^2 + \cdots + x^{k-1}y^{k-1}\right)^{n+1-m} = \frac{(1 - x^k y^k)^{n+1-m}}{(1 - xy)^{n+1-m}} $$

Now write out the series for $\frac{1}{(1 - xy)^{n+1-m}}$ explicitly, and expand $(1 - x^k y^k)^{n+1-m}$ with the binomial formula, and you should be able to find a finite summation yielding the coefficient of $x^{n+1} y^m$, which will equal $f(m,n,k)$.

Answer 2

As long as you're working on these types of problems in Wilf's book, you might also want to read a truly wonderful article by Noonan and Zeilberger on the Goulden-Jackson cluster method. It generalizes the above problem to avoid any collection of words (not just $k$ 1's in a row), and the method is no more complex than your calculation.