El problema siguiente es tomado del libro generatingfunctionology (P. 28) por Herbert S. Wilf.
Deje $f(n,m,k)$ el número de cadenas de $n$ $\,0$'s y $1$'s que contienen exactamente $m\,$ $1$'s, no $k$ de los cuales son consecutivos.
(a) Encontrar una fórmula de recurrencia para $f$. Se debe tener $f(n,m,k)$ en el lado izquierdo, y exactamente tres términos en el derecho.
(b) Encontrar, en simple forma cerrada, la generación de funciones $$ F_k(x,y)=\sum_{n,m\ge0}f(n,m,k)x^ny^m \,\,\,\,\,\,\,\,\ (k=1,2,...). $$ (c) Encontrar una fórmula explícita para $f(n,m,k)$ desde el genrating función (esto debe implicar sólo una sola suma, de una expresión que implica un par de factoriales).
Yo era capaz de resolver (a) y (b) y se encontró que la generación de funciones es $$ F_k = \frac{1-x^ky^k}{1-x-xy-x^{k+1}y^k} $$ Sin embargo, me parece no puede ser capaz de extraer la secuencia de esta función. Cualquier ayuda será apreciada.
Editar:
He añadido el camino he resuelto (a) y (b) para permitir que cualquier crítica en el caso de que tengo la función de malo. Mi solución (a) va como sigue:
Dado $m,n,k$ tal que $0\le k\le m \le n$$k\lt n$, nos fijamos en todos los de la cadena de bits de longitud $n$ que contienen exactamente $m$ $1$'s, no $k$ de los cuales son consecutivos. Hemos dividido estas cadenas en dos sets. El primero compuesto de todas las cadenas que terminan con $0$. Este conjunto ha $f(n-1,m, k)$ cadenas ya que mediante la eliminación de la $0$ desde el final de la cadena se obtiene una correspondencia uno a uno entre las cadenas en nuestro juego y las cuerdas $f(n-1,m, k)$ condes. El otro conjunto se compone de todas las cadenas que terminan con $1$. Quitando el último bit se obtiene una correspondencia uno a uno entre nuestro juego y todas las cadenas cuentan por $f(n-1,m-1, k)$, a excepción de aquellos que han $k-1$ consecutivo $1$'s al final. Para contar el último primero nos cuenta que desde $k\lt n$ debe haber otro poco, que deben ser $0$, antes de la última $k-1$ $\,1$'s. Por la eliminación de la última $k$ bits ($10\cdots0$) obtenemos una correspondencia uno a uno con las cadenas que se cuentan por $f(n-k-1,\,m-k,\,k)$. Con la que obtenemos la recursividad: $$f(n,m,k) = f(n-1,m,k) + f(n-1,m-1,k) - f(n-k-1,\,m-k,\,k)$$ Además, tomamos nota de la si $0\le m \le n$$k > m$, $f(n,m,k) = \binom{n}m$ , ya que no podemos tener más consecutivas $1$'s de los que hay a $1$'s, por lo que el problema se reduce a contar el número de cadenas de caracteres con una longitud de $n$ que han $m$ $1$'s. Para todos los demás casos escribimos $f(n,m,k) = 0$ que completa la definición.
Para Resolver (b) hice lo siguiente:
$$ \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} $$ Mediante el convenio que $\binom{n}m = 0$ al $m\gt n$, y señalando que, cuando $m=n\ge k$ tenemos $f(n,m,k)=0$ podemos escribir la ecuación anterior de la siguiente manera: $$ \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} $$ donde: $$\omega(x,y) := \frac{1 - (\frac{xy}{1-x})^k}{1 - \frac{xy}{1-x}}.$$ El uso de la recusion fórmula obtenida en (a), podemos expandir el segundo sumando así: $$ \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} $$ donde: $$ \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} $$ Sumando todos los valores, se obtiene: $$ 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 $$ Y así (tenga en cuenta que $\omega$ desaparece): $$ F_k = \frac{1-x^ky^k}{1-x-xy-x^{k+1}y^k} $$
