La generación de la Función para la Cadena Binaria Pregunta

Question

La siguiente es una asignación pregunta que he estado tratando de trabajar durante algún tiempo.

Deje $C(x,y)=\sum_{n,k \geq 0} c_{n,k} x^{n} y^{k}$ donde $c_{n,k}$ es el número de cadenas binarias de longitud $n$ $k$ bloques. Demostrar que $$\begin{equation} C(x,y)=\frac{1-x+yx}{1-x-yx} \end{equation}$$ A continuación, mostrar que $[x^{n}] \frac{\delta}{\delta y} C(x,y) \left|_{y=1} \right.$ es el número total de bloques de entre todas las cadenas binarias de longitud $n$.

Sé que el primer paso es encontrar una relación de recurrencia para $c_{n,k}$. Considere la posibilidad de un arbitrario cadena binaria de longitud $n$ $k$ bloques. El primer dígito es cero o uno; la diferencia es irrelevante. El segundo dígito es el mismo o por el contrario de que el primer dígito.

En el primer caso, cuando el segundo dígito es el mismo que el primero, hay $k$ bloques en el $(n-1)$ dígitos largo de la subcadena. El número de subcadenas es $c_{n-1,k}$. En el segundo caso, cuando el segundo dígito es diferente de la primera, a una cuadra ha sido encontrado y por lo $(k-1)$ bloques de permanecer en el $(n-1)$ dígitos largo de la subcadena. El número de subcadenas es $c_{n-1,k-1}$. Esto le da la siguiente relación de recurrencia: $$\begin{equation} c_{n,k}=c_{n-1,k}+c_{n-1,k-1}. \end{equation}$$

Si $k>n$, $c_{n,k}=0$ porque no hay manera de tener más bloques de dígitos de dígitos en una cadena binaria. Si $k=n$, $c_{n,k}=2$ debido a que hay dos cadenas binarias con la alternancia de dígitos.

Deje $C(x,y)= \displaystyle\sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k}$. Encontrar bivariado de generación de función. $$\begin{equation} \begin{aligned} \sum_{k=1}^{\infty} c_{n,k} y^{k} &= \sum_{k=1}^{\infty} c_{n-1,k} y^{k} + \sum_{k=1}^{\infty} c_{n-1,k-1} y^{k} \\ \sum_{n=1}^{\infty} \sum_{k=1}^{\infty} c_{n,k} x^{n}y^{k} &= \sum_{n=1}^{\infty} \sum_{k=1}^{\infty} c_{n-1,k} x^{n}y^{k} + \sum_{n=1}^{\infty} \sum_{k=1}^{\infty} c_{n-1,k-1} x^{n}y^{k} \\ \sum_{n=1}^{\infty} \sum_{k=1}^{\infty} c_{n,k} x^{n}y^{k} &= x\sum_{n=1}^{\infty} \sum_{k=1}^{\infty} c_{n-1,k} x^{n-1}y^{k} + xy\sum_{n=1}^{\infty} \sum_{k=1}^{\infty} c_{n-1,k-1} x^{n-1}y^{k-1} \\ \end{aligned} \end{equation}$$ $$\begin{equation} \begin{aligned} \sum_{n=0}^{\infty} \sum_{k=1}^{\infty} c_{n,k} x^{n}y^{k} - \sum_{k=1}^{\infty} c_{0,k}x^{0}y^{k} &= x\sum_{n=0}^{\infty} \sum_{k=1}^{\infty} c_{n,k} x^{n}y^{k} + xy\sum_{n=0}^{\infty} \sum_{k=1}^{\infty} c_{n,k-1} x^{n}y^{k-1} \\ \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k} - \sum_{n=0}^{\infty} c_{n,0} x^{n} &= x \left( \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k} - \sum_{n=0}^{\infty} c_{n,0} x^{n} \right) + xy\sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k} \\ \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k} - 2 &= x \sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k} - 2x + xy\sum_{n=0}^{\infty} \sum_{k=0}^{\infty} c_{n,k} x^{n}y^{k} \\ C(x,y)-1&= xC(x,y)-x+xyC(x,y) \\ (1-x-xy)C(x,y) &= 2-2x \\ C(x,y) &= \frac{2-2x}{1-x-xy} \end{aligned} \end{equation}$$

En este punto, estoy seguro de cómo proceder. Además, yo sé que claramente han cometido un error de arriba, pero no puedo encontrarla.

Cualquier ayuda se agradece!

Answer 1

La recurrencia puede ser escrito

$$c_{n,k}=c_{n-1,k}+c_{n-1,k-1}+[n=k=0]-[n=1][k=0]+[n=k=1]\;,$$

donde los corchetes son Iverson soportes; esto hace que la recurrencia válido para todos los $n,k\ge 0$ en el supuesto de que $c_{n,k}=0$ si $n$ o $k$ es negativo. Esta es una manera fácil de crear las condiciones iniciales en la recurrencia, y aunque no he estado en los detalles, parece como si esta es probablemente donde usted se fue un poco a la deriva.

Multiplicar la recurrencia a través de por $x^ny^k$ y suma más de $n,k\ge 0$:

$$\begin{align*} C(x,y)&=\sum_{n,k\ge 0}c_{n,k}x^ny^k\\\\ &=\sum_{n,k\ge 0}c_{n-1,k}x^ny^k+\sum_{n,k\ge 0}c_{n-1,k-1}x^ny^k+1-x+xy\\\\ &=xC(x,y)+xyC(x,y)+1-x+xy\;, \end{align*}$$

así

$$C(x,y)=\frac{1-x+xy}{1-x-xy}\;.$$