La pregunta es, ¿cuántos enteros entre 1 y 100000 tienen la suma igual a quince?
Respuesta
¿Demasiados anuncios?
Supongamos que se escribe el número $15$ como $a_1+a_2\dots a_n$ donde todos los números son enteros entre $1$ y $9$ . Entonces podemos hacer un montón de números entre $1$ y $1,000,000$ que se suman $15$ y cuyos dígitos no nulos son precisamente $a_1.a_2\dots a_n$ en ese orden. ¿Cuántos?
El número en cuestión debe tener $6$ dígitos o menos. Así que podemos sumar $6-n$ ceros y mirar los dígitos no nulos como barras para aplicar un argumento de estrellas y barras.
De este modo, los ceros son las estrellas y los dígitos no nulos son las barras. Por lo tanto, hay $\binom{6}{n}$ formas de disponer los ceros entre los dígitos no nulos. (Las configuraciones que tienen ceros en las ranuras más a la izquierda representan los números con menos dígitos).
Así que podemos idear un método para contar todos los números.
Dejemos que $f(k)$ sea el número de formas de escribir $15$ como una suma ordenada de $k$ enteros entre $1$ y $9$ que suman $15$ .
Entonces la solución es $\sum_{k=1}^6f(k)\binom{6}{k}$
¿Cómo calculamos $f(k)$ ?
Obsérvese que es el coeficiente de $x^{15}$ en la expresión $(x+x^2\dots+x^9)^k$
Como señala Brian. El problema se reduce a esto:
Hay seis ranuras (cada una de ellas representa uno de los dígitos). Debemos distribuir $15$ canicas entre ellos para que ninguno tenga más de $9$ canicas.
el número de formas de hacerlo es el coeficiente de $x^{15}$ en $(1+x+x^2\dots x^9)^6$
¿Por qué es lo mismo que $\binom{20}{5}-6\binom{10}{5}$ ?
De nuevo un Brian señala que hay $\binom{20}{5}$ formas de separar el $15$ canicas en $6$ cajas por estrellas y barras sin tener en cuenta los límites de tamaño.
¿Cuántas formas violan el límite de tamaño? Observa que como máximo una de las cajas puede tener más de $9$ canicas.
Cuántas formas de salir de la caja $1$ con más de $9$ ¿mármoles?
Supongamos que tienes una configuración de este tipo. entonces quita el $10$ canicas de la caja $1$ y se queda con una distribución de $5$ canicas en $6$ cajas por estrellas y barras hay $\binom{10}{5}$ de estos.
Dado que hay $6$ opción para la caja que tiene demasiados $marbles$ tenemos que restar $6\binom{10}{5}$ del recuento.
