4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ So if I understand correctly, the result should be: $$ \sum_{r}(-1)^r\binom{n-m+1}{r}\binom{n-rk}{n-m}$$ $\endgroup$ – SomeStrangeUser Mar 7 '14 at 13:03
  • 1
    $\begingroup$ @SomeStrangeUser I get the same thing. I have also just checked directly that it satisfies the recursion and the base cases. $\endgroup$ – 6005 Mar 7 '14 at 15:55
  • $\begingroup$ @SomeStrangeUser Thanks for the edit. I'm going to roll back to the larger square brackets because I think they look nicer, and I don't see any danger of confusing them with the floor function (which is \lfloor...\rfloor, $\lfloor \cdot \rfloor$). $\endgroup$ – 6005 Mar 9 '14 at 11:52
1
$\begingroup$

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.

$\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.