Número de cadenas binarias con $n$ y $m$ ceros

Question

$f(n,m)$ es el número de cadenas binarias con hasta $n$ y hasta $m$ ceros.

Demuestra que el número de cadenas posibles es: $${n+m+2 \choose n+1} -1$$

Llegué al punto de que: $$\sum_{a=0}^n \sum_{b=0}^m {a+b \choose a}$$

Y también entiendo que hay $(n+1)$ opciones para la cantidad de unos y $(m+1)$ opciones para la cantidad de ceros.

Answer 1

Dejemos que $S$ sea el conjunto de cadenas binarias de longitud $n+m+2$ con $n+1$ y $m+1$ ceros. Por definición, $$|S|=\binom{n+m+2}{n+1}.$$

Dejemos que $L \in S$ . Sea $\beta$ sea el bit en el último lugar de $L$ y $\overline{\beta}$ sea el complemento de $\beta$ .

Desde $n \geq 0$ y $m \geq 0$ Sabemos que $L$ tiene la forma $$L=(\text{substring } X,\overbrace{\overline{\beta},\overline{\beta},\ldots,\overline{\beta}}^i,\overbrace{\beta,\beta,\ldots,\beta}^j)$$ donde $i \geq 1$ (y $i$ es el máximo número entero positivo posible) y $j \geq 1$ . Observamos:

• La subcadena $X$ obtenido es una cadena binaria con un máximo de $n$ y como máximo $m$ ceros.

• Toda cadena binaria no vacía $X$ con un máximo de $n$ y como máximo $m$ Los ceros se pueden obtener de forma única de esta manera (añadiendo unos y ceros de forma adecuada).

• La cadena binaria vacía $X$ puede obtenerse exactamente de dos maneras.

Por lo tanto, hay $|S|-1$ cadenas binarias con un máximo de $n$ y como máximo $m$ ceros.

Answer 2

Como ha comentado Daniel Fischer más arriba, puedes aplicar las identidades del "palo de hockey" para encontrar tu suma; son las sumas que bajan por las diagonales del triángulo de Pascal:

Para la suma interna, utilice

$\binom{a}{a}+\binom{a+1}{a}+\binom{a+2}{a}+\cdots+\binom{a+m}{a}=\binom{a+m+1}{a+1}$ ;

y para la suma exterior, utilice

$\binom{m+1}{0}+\binom{m+1}{1}+\binom{m+2}{2}+\cdots+\binom{m+n+1}{n+1}=\binom{m+n+2}{n+1}$ .

(La primera suma va por una diagonal de derecha a izquierda, y la segunda suma baja por una diagonal de izquierda a derecha).

Answer 3

Podemos encontrar la suma generando funciones \begin{align*} \sum_{b=0}^{m} \binom{a+b}{b} &= [x^m] \frac{1}{(1-x)}\frac{1}{(1-x)^{a+1}} \\ \implies \sum_{a=0}^{n} \sum_{b=0}^{m} \binom{a+b}{b} &= [x^m]\sum_{a=0}^{n}\frac{1}{(1-x)^{a+2}} \\ &= [x^m]\left(\frac{1}{x\left(1-x\right)^{n+2}}-\frac{1}{x\left(1-x\right)}\right) \\ &= \binom{m+n+2}{m+1}-1 \end{align*}