5 votos

Distribuir los regalos para que todos reciban al menos uno

Así que estaba en clase discutiendo el siguiente problema: "tenemos $20$ diferentes regalos para distribuir a $12$ niños. No es necesario que todos los niños reciban algo; incluso podría ocurrir que diéramos todos los regalos a un solo niño. ¿De cuántas maneras podemos distribuir los regalos?". Después de discutirlo, nos dimos cuenta de que la respuesta era $12^{20}$ porque el problema sólo podría resolverse si lo viéramos desde la perspectiva de los regalos y no de los niños. A mí me pareció muy bien.

Luego me fui a casa y pensé en un corolario del problema: ¿cuántas formas hay para que cada niño reciba al menos un regalo? Llevo una semana pensando y no consigo resolverlo. Pensé que era $12^{12} \times 12^8$ El primer número representa los regalos que se reparten al menos a un niño y el otro los que se reparten sin discriminación. Sin embargo, ese número es mayor que el número original de formas, lo que no tiene sentido. ¿Cómo resolverías esto?

4voto

N. F. Taussig Puntos 8718

Como ha observado, hay $12^{20}$ formas de distribuir los regalos sin restricciones. Hay $\binom{12}{k}$ maneras de excluir $k$ de los destinatarios de recibir un regalo y $(12 - k)^{20}$ formas de distribuir los regalos a los restantes $12 - k$ personas. Por el Principio de inclusión-exclusión el número de formas de distribuir los regalos para que cada persona reciba al menos uno es $$\sum_{k = 0}^{12} (-1)^k\binom{12}{k}(12 - k)^{20}$$

1voto

Foobaz John Puntos 276

He aquí una forma de resolver el problema utilizando funciones generadoras exponenciales. Obsérvese que $$ F(x)=(e^x-1)^{12}=\left(x+\frac{x^2}{2!}+\dotsb\right)^{12}=\sum_{n=0}^{\infty}\left(\sum_{k_i>0} \binom{n}{k_1, k_2, \dotsc,k_{12}}\right) \frac{x^n}{n!} \tag{1} $$ Por lo tanto, buscamos el coeficiente de $x^{20}/20!$ en el lado derecho de (1). Pero también tenemos que $$ F(x)=(e^x-1)^{12} =\sum_{k=0}^{12}\binom{12}{k}(-1)^k e^{(12-k)x} =\sum_{k=0}^{12}\binom{12}{k}(-1)^k\left(\sum_{m=0}^{\infty} (12-k)^m\frac{x^m}{m!} \right) \tag{2} $$ por el teorema del binomio. En particular, el coeficiente de $x^{20}/20!$ en el lado derecho de (1) y, por tanto, el número de vías es $$ \sum_{k=0}^{12}\binom{12}{k}(-1)^k (12-k)^{20}. $$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X