Argumentando la corrección de una alternativa, secuencias de manera de contar cuántos bits con exactamente n ceros y k +1 son allí

Question

Yo estaba tratando de contar cuántas secuencias de bits con exactamente n ceros y k+1 están allí.

Uno de los aspectos que el razonamiento es sólo por hacer lo $ \binom {k+n+1}{k+1}$, haciendo elegir.

Sin embargo, me dijeron que usted también puede hacerlo de la siguiente suma:

$$\sum^{n}_{i=0}\binom {k+i}{k}$$

Si eso es cierto, entonces:

$$\sum^{n}_{i=0}\binom {k+i}{k} = \binom {k+n+1}{k+1}$$

Que después de un montón de álgebra que voy a omitir, y puede ser verificado por inducción! Increíble. Sin embargo, estoy seguro de cuál es el razonamiento combinatorio. ¿Alguien sabe cómo motivo combinatorio para establecer la igualdad? Se puede también justificar la corrección de su argumento?

De hecho, me dijeron que la siguiente es la "correcta" de razonamiento, aunque yo no puedo hacer sentido de por qué su correcta:

Por otro lado, el número de ceros de la i a la izquierda de la derecha uno de los rangos de 0 a n. Para un valor fijo de i, hay $\binom {k+i}{k}$ posible opciones para la secuencia de bits antes de la de más a la derecha uno. Si tenemos la suma de todos los yo posibles, nos encontramos con que el número que queremos es $\sum^{n}_{i=0} \binom {k+i}{k}$

Mi principal preocupación es con la suma. No puedo entender la interpretación de la suma. Es de suma a más de subconjuntos disjuntos? O ¿por qué es resumir las cosas? La única vez que he visto sumas en contar es cuando hay subconjuntos disjuntos (o con el de la inclusión principio de exclusión).

Incluso si usted me explique lo que la interpretación de los medios, creo que no puede ser demasiado útil a menos que haya una explicación de su corrección.

---

Por favor proporcione detalles sobre el combinatoric interpretación de la suma, la parte de la pregunta que estoy teniendo problemas para entender. Eso es, supongo que lo que me está dando problemas. No veo por qué esta descripción da la deseada igualdad.

Por ejemplo, uno de los aspectos que me hubiera gustado que abordar es, ¿cómo es que la suma NO doble contabilidad? A medida que aumenta, combinaciones de los anteriores pasos se "reconsidere"...o no? A mí me parece que son. A continuación, si lo son, ¿por qué es que la suma NO doble contabilidad?

---

RECOMPENSA

Yo no soy capaz de poner una recompensa, pero la respuesta que justifica la corrección bastante bien y me convence de aceptar su respuesta, con mucho gusto le recompensa cuando llegue el momento.

Hacer es que si no es aceptado respuesta, aún no he tenido mi confusión/duda aclarada.

Answer 1

Respuesta corta:
Recuento de todos los arreglos de la k+1 queridos propagación de la posición 1 a la posición k+i+1

Largo:
En el k+n+1 posiciones,
coloque un '1' en la posición k+i+1. Este es el centinela elemento. Distribuir el resto k '1'-s de la posición 1 a la posición k+i. Esto se puede hacer en $${k+i\choose k}$$ maneras.

De esta manera usted tiene un arreglo en donde '1'-s se reparten entre las posiciones 1 y k+i+1 (ambos inclusive). Resto de las posiciones son, por supuesto, '0'-s

La suma de estos sobre todos i (0 <= i <= n ) y usted tendrá todo el arreglo de k+1 1 y n '0'-s, con k+n+1 posiciones.

Answer 2

La idea detrás de hacer que suma es que se está clasificando de acuerdo a cuántos ceros antes de venir a la de la última. Dado que el número de ceros antes de que la última puede ser cualquier número de $0$ $n$podemos obtener la deseada bijection.

Otra manera de ver por qué la identidad de $\binom{n+k+1}{k+1}=\sum\limits_{i=0}^n\binom{k+i}{k}$

es de notar la mano izquierda nos está diciendo el número de subconjuntos de tamaño $k+1$ del conjunto de $\{1,2,3\dots n+k+1\}$, Mientras que el lado derecho es el que nos da el número de subconjuntos de tamaño $k$ $\{1,2,3,4\dots k\}$ más el número de subconjuntos de tamaño $k$ $\{1,2,3\dots k+1\} \dots$ más el número de subconjuntos de tamaño $k$ $\{1,2,3\dots k+n\}$

Ahora considere una subconjuntos $A$ $k+1$ elementos de las $\{1,2,3\dots,n+k+1\}$ , vamos a $w$ ser su elemento más grande. Vamos a asignar a este subconjunto subconjunto del conjunto $\{1,2,3\dots w-1\}$ que consta de todos los elementos en $A$ con la excepción de $w$. Usted debe comprobar que esta función es de hecho un bijection entre los subconjuntos de contado en el lado izquierdo y los subconjuntos se cuentan en el lado derecho.

Answer 3

Tomando $A_i$ a ser el conjunto de secuencias en las que el número de ceros a la izquierda de la derecha dígito uno es $i,$ y hacer esto una vez para cada una de las $i=0,\ldots,n,$ no en el hecho de dar $n+1$ conjuntos disjuntos $$A_0,\ldots,A_n.$$ Ningún elemento de $A_p$ $A_q$ cualquier $p\neq q,$ porque siempre se puede simplemente contar el número de ceros a la izquierda de la derecha en cualquier finito de bits de la secuencia. Ese número puede ser $p,$ o puede ser $q,$ pero no puede ser $p$ $q.$

Por otra parte, cualquier secuencia de $n$ ceros y $k+1$ debe ser en uno de los conjuntos $A_0,\ldots,A_n,$ nuevo porque usted puede simplemente contar el número de ceros a la izquierda de la derecha. Ese número no puede ser mayor que $n$ (porque entonces no sería más que $n$ ceros en total, en ese orden) y ciertamente, no se puede menos de $0.$

De manera que los conjuntos $A_0,\ldots,A_n$ son una partición del conjunto de todas las secuencias de $n$ ceros y $k+1$, y el tamaño del conjunto es $|\bigcup A_i| = \sum |A_i|.$

EDIT: he Aquí un ejemplo específico que espero que pueda ayudar a visualizar el caso general descrito anteriormente:

Para $n=2$ $k=2,$ hemos $$\begin{eqnarray} A_0 &=& \{ 11100 \},\\ A_1 &=& \{ 11010, 10110, 01110 \},\\ A_2 &=& \{ 11001, 10101, 01101, 10011, 01011, 00111 \}.\\ \end{eqnarray}$$

Cada conjunto en este ejemplo es exactamente como me lo describió para el caso general (por ejemplo, el número de ceros a la izquierda de la derecha es exactamente $2$ en cada elemento de a $A_2$) y como se puede ver, no hay duplicados.