Distribuir $15$ caramelos a $5$ niños con restricciones

Question

Supongamos que quiere distribuir $15$ caramelos a $5$ diferentes niños.

(a) ¿De cuántas maneras se puede hacer esto si ningún niño recibe más de $6$ ¿caramelos?

(b) ¿De cuántas maneras se puede hacer esto si cada niño termina con un número diferente de caramelos?

Ya hemos determinado que el número de formas de distribuir los caramelos a los $5$ niños de tal manera que cada niño reciba al menos una pieza es $1,001$ formas.

¿Cómo nos ocupamos de la restricción de que cada niño no reciba más de $6$ ? ¿Podemos tomar el complemento y restar el número de formas en que un niño recibe $7-15$ ¿piezas? ¿O sería un intento largo e innecesario?

Mi intento:

Considere el complemento en el que un niño recibe al menos $7$ caramelos.

Paso $1$ : Elige al niño que va a recibir $7$ caramelos y dale el $7$ caramelos: $5$ opciones

Paso $2$ : Distribuya el resto $15-7=8$ caramelos a la $5$ niños.

Hay $\binom{8+4}{4}=\binom{12}{4}=495$ formas de hacerlo.

Así que hay $5\cdot 495=2,475$ formas de distribuir los caramelos de manera que un niño reciba al menos $7$ caramelos.

Hay $\binom{15+4}{4}=\binom{19}{4}=3,876$ maneras de distribuir los caramelos sin ninguna restricción.

Así que hay $3,876-2,475=1,401$ formas de distribuir los caramelos de manera que ningún niño reciba más de $6$ caramelos.

Answer 1

(a) Considerar en el anillo $\Bbb Q[x]/x^{16}$ el siguiente producto de cinco factores iguales: $$ \left(\ x+x^2+x^3+x^4+\dots+x^{15}+O(x^{16})\ \right)^5\ . $$ El coeficiente $C$ de $x^{15}$ en este producto es exactamente el número de posibilidades de partición $15$ en cinco partes $\ge 1$ . (Utilizamos polinomios generadores / series).

Simplificamos con $x^5$ y buscar el coeficiente $C$ de $x^{10}$ en $$ \left(\ 1+x+x^2+x^3+x^4+\dots\ \right)^5=\frac 1{(1-x)^5}\ . $$ Aquí utilizamos series de potencias formales o polinomios modulo algunos adecuados $O$ de algún poder de $x$ .

Esto se puede calcular comenzando con $(1-x)^{-1}=1+x+x^2+x^3+\dots$ y aplicamos la derivada formal cuatro veces más. El coeficiente en grado $10$ proviene del que está en grado $14$ Así que es $C=(14\cdot 13\cdot 11\cdot 10)/(-1)(-2)(-3)(-4) =\binom{14}4$ . Como en el OP. Hasta ahora nada nuevo.

---

Para obtener el número $C'$ de particiones con un máximo de $6$ velas consideren en cambio: $$ \left(\ x+x^2+x^3+x^4+x^5+x^6\ \right)^5\ . $$ y aislar el coeficiente de $x^{15}$ en él. De manera equivalente, encuentre el coeficiente de $x^{10}$ en $$ \left(\ 1+x+x^2+x^3+x^4+x^5\ \right)^5=\frac {(1-x^6)^5}{(1-x)^5}\ , $$ que es $$ \Big[\ 1-5x^6+\dots\ \Big] \left[\ \binom 44 + \binom 54 x + \binom 64 x^2 + \binom 74 x^3 + \binom 84 x^4 + \dots + \binom {14}4 x^{10} +\dots\ \right] $$ El coeficiente que necesitamos es $C'=\binom {14}4-5\binom 84=651$ . De nuevo, lo mismo que en el OP, tras la siguiente pequeña corrección.

El primer paso consiste en elegir el hijo que se $6+$ al menos un caramelo más. Así que tenemos que distribuir "en las mismas condiciones" el $15-6=9$ más caramelos. Esto conduce al coeficiente binomial $\binom{9-1}{5-1}$ de la misma manera que para el total tenemos $\binom{15-1}{5-1}=1001$ posibilidades.

Consulte con sage :

sage: R.<x> = QQ[]
sage: P = ( x + O(x^16) ) / (1-x)
sage: P^5 + O(x^16)
x^5 + 5*x^6 + 15*x^7 + 35*x^8 + 70*x^9 + 126*x^10 + 210*x^11 + 330*x^12 
    + 495*x^13 + 715*x^14 + 1001*x^15 + O(x^16)
sage: Q = ( x + O(x^16) ) * (1-x^6) / (1-x)
sage: Q
x + x^2 + x^3 + x^4 + x^5 + x^6 + O(x^16)
sage: Q^5 + O(x^16)
x^5 + 5*x^6 + 15*x^7 + 35*x^8 + 70*x^9 + 126*x^10 + 205*x^11 + 305*x^12 
    + 420*x^13 + 540*x^14 + 651*x^15 + O(x^16)

(Los resultados se rompieron manualmente para ajustarlos a la anchura).

---

(b) Observa que la suma mínima de cinco enteros positivos diferentes es $$1+2+3+4+5=15\ .$$

Answer 2

Debido a los valores particulares elegidos para este problema, no es demasiado difícil hacerlo tomando el complemento, aunque se hace más difícil en general. Para cada uno de los $5$ niños, considere el caso de que ese niño obtenga al menos $7$ . Queremos calcular el tamaño del conjunto $S_i$ , para $1\leq i\leq 5$ para cada uno de los niños. Una vez que le des $7$ al niño $i$ , se pueden contar las composiciones débiles de los restantes $8$ en $5$ partes utilizando estrellas y barras.

A continuación, para cada uno de los $5$ niños, hemos contado el número de formas en que el niño $i$ obtiene al menos $7$ piezas, que ponemos en el conjunto $S_i$ . Si los restamos del número total de distribuciones sin restricción, obtenemos el número deseado. Pero hay un problema: ¿qué pasa si una distribución que da a los niños $i$ al menos $7$ piezas también da a los niños $j$ al menos $7$ ¿piezas? Entonces lo contaríamos una vez en $S_i$ y de nuevo en $S_j$ , lo que significa que lo restamos dos veces del número total de distribuciones, lo que sería incorrecto. Eso significa que habría que volver a sumar el número de distribuciones que dan dos hijos diferentes al menos $6$ piezas, para que no cuentes dos veces tus casos malos.