Tengo un problema que dice
"¿Cuántas maneras existen van a dar $k$idéntico a las galletas a $n$-los niños son distintos, si cada niño reciba, al menos, una galleta?"
Pensé que había que hacerlo usando la secuencia binaria. Mi enfoque es el uso de $1$'s como niños (separadores) y $0$'s como galletas. Ya que cada niño debe tener al menos una galleta, a continuación, la secuencia no puede comenzar con uno (no habría ningún $0$'s "galletas" a la izquierda) y no puede ser $1$'s uno al lado del otro (algunos $1$ "niño" tendría ninguna galleta). Ahora que ya sé la respuesta a ese problema y es $\binom{k-1}{n-1}$, y mi problema es la comprensión de por qué es $k-1$ e no $k$. Claramente $n-1$ es debido a que sólo se necesita $n-1$ separadores de tener $n$ divisiones, pero ¿por qué no es $k$ en lugar de $k-1$? Creo que tenemos $k$ lugares para $1$'s de lugar y no de $k-1$.
Respuestas
¿Demasiados anuncios?
Primero debemos darle a cada niño una galleta para que $k-n$ galletas.
A continuación, con las estrellas y las barras nos encontramos con $$\binom{k-n+(n-1)}{n-1}=\binom{k-1}{n-1}$$posibilidades.
SUGERENCIA:
Usted debe comenzar por dar a cada niño una galleta primer lugar, para que la condición se resuelve. Piensa acerca de cómo muchas galletas están a la izquierda y en cuántas maneras se puede distribuir entre los $n$ niños.
Espero que esta ayuda :)
Para este tipo de problemas generación de funciones también puede ser un buen enfoque. Pero en este caso yo lo consideraría un rebasamiento.
Para la secuencia binaria enfoque:
Usted tiene un $0$ al comienzo de la secuencia. Porque un "$1$" siempre es seguida por un "$0$", usted puede construir el resto de la secuencia por poner $n-1$ subcadenas "$10$" e $k-n$ subcadenas "$0$". Así que usted ha $n-1$ elementos de un tipo y $k-n$ de otro tipo, así que usted consigue $$ \binom{(n-1)+(k-n)}{n-1} = \binom{k-1}{n-1} $$ como el número de maneras.
Una asignación de $k$ galletas a $n$ de los niños con cada niño que recibe en menos de una galleta puede ser representado por las estrellas y barras. Por ejemplo, si $k=5$, e $n=4$ y la distribución es $(1,2,1,1)$, se puede representar por $$ \estrellas\mid\estrellas\,\estrellas\mid \estrellas\mid\estrellas $$ La elección de $n-1$ bares de $k-1$ "brechas" entre estrellas, únicamente define una distribución. Por lo tanto, hay $$ \binom{k-1}{n-1} $$ distribuciones. Alternativamente, usted puede utilizar el método de generación de funciones. De hecho, tenga en cuenta que $$ F(x)=\frac{x^n}{(1-x)^n}=(x+x^2+\dotsb)^n=\sum_{k=0}^\infty\left( \sum_{\alpha_1+\dotsb\alpha_n=k;\, \alpha_i\geq1} x^{\alpha_1+\dotsb\alpha_n}\right). $$ De ahí su basta para encontrar el coeficiente de $x^k$$F(x)$. Pero $$ [x^k]F(x)=[x^{k-n}](1-x)^{-n}=\binom{n+(k-n)-1}{n-1}=\binom{k-1}{n-1} $$ donde hemos usado el teorema del binomio $$ (1-x)^{-n}=\sum_{k=0}^{\infty}\binom {n}{k}(-1)^kx^k =\sum_{k=0}^{\infty}\binom{n+k-1}{n-1}x^k. $$
