Contar cadenas de bits

Question

Dados enteros $m$ y $n$ tal que $0 \le m \le n$ ,

1. ¿Cuál es el número total de cadenas de bits de longitud $n + 1$ y tienen exactamente $m$ 1's?

2. Considere un número entero $l$ tal que $0 \le l \le m$ . ¿Cuántas cadenas de bits de longitud $n + 1$ tienen exactamente $m$ 1, y empezar con $l$ copias de 1? (es decir $\underbrace{1,\dotsc,1}_{l},0\dotsc,0$ )

En primer lugar, creo que se trata de una simple cuestión de recuento. De los $n + 1$ elementos que estoy tratando de elegir m 1 por lo que creo que la respuesta es $n + 1 \choose m$ . Estoy atascado en la segunda parte y no estoy seguro de cómo determinar este número. Estaba intentando visualizarlo dibujando una matriz que fuera $n+1$ * $n+1 \choose m$ . Siendo el primer grupo de cadenas de bits las que empiezan por 1 de longitud $l$ . Creo que esto está mal así que si alguien tiene alguna sugerencia mejor que sería impresionante.

Gracias

Answer 1

1. Tenemos $n+1$ bits, y tenemos que elegir $m$ de ellos sean 1's, así que tenemos $\binom{n+1}m$ cadenas de bits de longitud $n+1$ y tienen exactamente $m$ 1's.

2. Sabemos que la cadena debe empezar por $l$ 1's, lo que hace que la parte restante de la longitud de la cadena $n-l+1$ con $m-l$ 1, así que tenemos que elegir $m-l$ bits del total $n-l+1$ bits sean 1's, por lo que tenemos $\binom{n-l+1}{m-l}$ cadenas de bits de longitud $n+1$ tienen exactamente $m$ 1, y empezar con $l$ copias de 1.

Espero que esto ayude.