Problème de combinatoire d'exclusion d'inclusion.

Question

Sept personnes laissent leurs vestes sur un support. De combien de façons leurs vestes peuvent-elles être retournées pour que personne ne récupère son propre manteau?

Cela invoque clairement le principe d'exclusion d'inclusion du formulaire:

$$ |\bar{A_1} \cap \bar{A_2} \cap \cdots \bar{A_n}| = |X| - \sum^n_{k=1}\sum_{1\leq i_1 < i_2 < \ldots < i_k\leq n}(-1)^{k+1}|{A_{i_k}} \cap {A_{i_2}} \cap \cdots {A_{i_n}}|$$

où $\bar{A_1}$ une personne ne récupère pas sa veste, $\bar{A_2}$ est la personne 2, et ainsi de suite.

Donc $A_1$ est le nombre de permutations où la personne 1 récupère sa veste, ce qui devrait être égal $6!$ comme thats combien de façons nous pouvons permuter les vestes des 6 personnes restantes.

$A_1\cap A_2$puis est le nombre de permutations où la personne 1 et 2 récupère sa veste, qui est 5! etc.

Ainsi est la réponse

$$ = 7! - (6! - 5! + 4! -3! + 2! -1! + 0! ) = 4420$$

est-ce correct? Ou dois-je tenir compte de cela pour le$A_1$ cas il y a $\binom{7}{1}$ les moyens de choisir la personne qui récupère sa veste, $\binom{7}{2}$ comment choisir les deux personnes qui récupèrent leur veste, et ainsi de suite?

Si cela est vrai, le cas de 6 personnes serait-il seulement = 1? Parce que même si ce modèle suggère$\binom{7}{6}\cdot 1$moyens d'avoir exactement 6 personnes avec les bonnes vestes, je ne vois pas comment cela pourrait être possible. Si tout le monde sauf 1 a la bonne veste, la dernière personne doit également avoir la bonne veste. Donc, selon cette logique, la réponse devrait être

$$ = 7! - (\binom{7}{1}6! - \binom{7}{2}5! + \binom{7}{3}4! -\binom{7}{4}3! + \binom{7}{5}2! -\binom{7}{6}1! + \binom{7}{7}0! ) = 1854$$

S'il vous plaît laissez-moi savoir si j'ai fait une erreur quelque part, tout conseil serait apprécié!

Answer 1

Une permutation de $n$les objets tels qu’aucun objet ne reste dans sa position initiale est appelé un dérangement . Vous demandez donc le nombre de dérangements de sept objets, c'est-à-dire le$7$-ème numéro de dérangement, qui est $1854$.

Votre approche pour calculer ce nombre au moyen de l'inclusion-exclusion est bonne. Votre premier argument, cependant, est faux. Vous avez en effet énormément mal compté les chiffres$A_i$. Par exemple, comme vous le remarquerez plus tard, il est impossible pour exactement six personnes de récupérer leur propre veste. Après tout, la seule personne restante doit alors obtenir la seule veste restante, qui doit alors être correcte également.

Pour un autre exemple, le nombre de façons au moins $5$ les gens peuvent avoir leur propre veste $$1+\tbinom{7}{5}=22.$$Après tout, soit chacun récupère sa propre veste, soit exactement $5$ les gens récupèrent leur propre veste.

Votre deuxième argument commence dans la bonne direction. Mais je ne sais pas du tout comment vous obtenez:

Donc, selon cette logique, la réponse devrait être $$= 7! - (\binom{7}{1}6! - \binom{7}{2}5! + \binom{7}{3}4! -\binom{7}{4}3! + \binom{7}{5}2! -\binom{7}{6}1! + \binom{7}{7}0! ) = 1854.$$

Le nombre qui apparaît est correct, mais l'argument est manquant.