nnn invitados, cada invitado trae un premio, ¿de cuántas maneras se pueden repartir los premios para que nadie reciba el premio que trajeron?

Marquemos cada premio del 1 al n, p1, p2, p3, ... pny las personas en los invitados a la fiesta g1, g2, g3, ... gn, ¿dónde piestá el premio del invitado gi? Tu objetivo es asegurarte de no hacer coincidir los premios con los invitados que tienen los mismos índices. En este caso, debe asegurarse de que: p1 no vaya a g1, p2 no vaya a g2, p3 no vaya a g3, y así sucesivamente. Consideremos |S|el caso en el que al menos un invitado recibe el mismo premio. En este caso podemos escribir |S|así:

En su caso, necesita lo contrario (la cantidad de formas en que las personas NO reciben el mismo premio), por lo que lo que debe hacer es restar del total de formas en que puede distribuir los premios |S|. El número total de formas de distribuir los n premios es$n^n$(no n-1 ya que necesita contar para el caso cuando la persona no recibe nada. Por lo tanto:

Los trastornos cuentan la situación en la que cada invitado recibe exactamente 1 premio. Sin embargo, la redacción OP dice que cada invitado puede obtener CUALQUIER número de premios (es decir,$0$a$n-1$ya que no puede obtener su propio premio). En este caso, la respuesta correcta es de hecho$(n-1)^n$, porque cada uno de$n$los premios pueden ir a cualquiera de$(n-1)$destinatarios Es decir, tu maestro se equivoca al marcarte mal.

Si su maestro insiste en usar Inclusión Exclusión, entonces deje que$A_i$ser el conjunto de arreglos st persona$i$recibe su propio regalo. Entonces IE da:

$answer = n^n - \sum_i |A_i| + \sum_{i<j} |A_i \cap A_j| - \sum_{i<j<k} |A_i \cap A_j \cap A_k| + ...$

Ahora,$|A_i| = n^{n-1}$desde el otro$n-1$los obsequios no tienen restricciones y cada uno puede ir a cualquiera de$n$destinatarios Similarmente,$|A_i \cap A_j| = n^{n-2}$porque el otro$n-2$los obsequios no tienen restricciones y cada uno puede ir a cualquiera de$n$destinatarios Del mismo modo para términos más altos. Entonces:

$answer = n^n - {n \choose 1} n^{n-1} + {n \choose 2} n^{n-2} - {n \choose 3} n^{n-3} + ... = \sum_{k=0}^n {n \choose k} (-1)^k n^{n-k}$

Pero la última suma es exactamente la expansión binomial de$(n-1)^n$.