Conteo de palabras binarias por carreras

Question

Me gustaría contar el número de binario palabras que han $m$ ceros, $n$ queridos y $k$ carreras de la (bloques consecutivos de). Llamarlo $a(m,n,k)$. He tratado de aplicar el método simbólico y se introdujo la clase $\cal{A} = \{\text{ binary words } \}$ y la generación de la función

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

donde $|\alpha|_k$ es el número de dígitos $k=0,1$ $\alpha$ $|\alpha|_r$ es el número de carreras de.

Ahora creo que el siguiente tiene (ya que una palabra tiene cierta cantidad de, como el de la primera ejecución (con una cierta cantidad de ceros delante), o no tiene)

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

Y de esto podemos obtener una ecuación para la generación de la función:

$$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 + \frac{1}{1-x} $$ Y por lo tanto $$ \\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}\, seleccione{m}}{{-k}\, seleccione{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}\, seleccione{m-k}}{{-k}\, seleccione{n-k}} x^{m}y^{n}z^k $$

Desde aquí podemos ver la solución

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

Pero creo que esto es incorrecto, ya que por ejemplo para $m=0$ se debe tener siempre a $1$, pero en mi resultado, el primer factor que hará $0$. Dónde está mi error? Mi fuente para el problema es que esta tarea la pregunta 2 y también hay soluciones en la página, pero me gustaría resolver yo mismo.

Answer 1

Como mencioné en un comentario, no contando las cadenas que terminan con una $1$. Es decir, dejando $\mathcal B=\{\text{binary words ending in 0}\}\cup\{\epsilon\}$, y dejando $B(x,y,z)=\sum_{\beta\in \mathcal B}x^{|\beta|_0}y^{|\beta|_1}z^{|\beta|_r}$, han demostrado que $$ B(x,y,z)= \sum_{m\geq k} \sum_{n\geq k} \sum_{k\geq 0} {{m}\, seleccione{k}}{{n-1}\, seleccione{k-1}} x^{m}y^{n}z^k $$ Sin embargo, hay una solución rápida. Usted puede notar que $$ xA(x,y,z)+1=B(x,y,z) $$ correspondiente a la ecuación de $\mathcal B=(\mathcal A\times \{0\})\cup \{\epsilon\}$. Esto le da a usted

$$ A(x,y,z)= \sum_{m\geq k} \sum_{n\geq k} \sum_{k\geq 0} {{m}\, seleccione{k}}{{n-1}\, seleccione{k-1}} x^{m-1}y^{n}z^k $$ La extracción de la $[x^my^nz^k]$ coeficiente, consigue $\binom{m+1}{k}\binom{n-1}{k-1}$.

---

Aquí es un método diferente que funciona; vamos a

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

Luego de recibir el mutuo recurrencia $$ \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} $$ que, dejando $M$ $N$ ser las correspondientes funciones de generación, implica $$ \begin{align} M&=\frac{x}{1-x}N + \frac1{1-x}\\ N&=\frac{yz}{1-y}M \end{align} $$ Usted puede resolver este sistema por $M$$N$. Concluye señalando $A=M+N$.