Einschluss Ausschluss Kombinatorisches Problem.

Question

Sieben Personen lassen ihre Jacken auf einem Gestell liegen. Auf wie viele Arten können ihre Jacken zurückgegeben werden, damit niemand seinen eigenen Mantel zurückbekommt?

Dies ruft eindeutig das Einschlussausschlussprinzip des Formulars hervor:

$$ |\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}}|$$

wo $\bar{A_1}$ ist 1 Person nicht seine Jacke zurück, $\bar{A_2}$ ist Person 2 und so weiter.

so $A_1$ ist die Anzahl der Permutationen, bei denen Person 1 seine Jacke zurückbekommt, was gleich sein sollte $6!$ So viele Möglichkeiten können wir die Jacken der verbleibenden 6 Personen durchdringen.

$A_1\cap A_2$dann ist die Anzahl der Permutationen, bei denen Person 1 und 2 ihre Jacke zurückbekommen, was 5 ist! und so weiter.

So lautet die Antwort

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

ist das richtig? Oder muss ich das für die berücksichtigen$A_1$ Fall gibt es $\binom{7}{1}$ Möglichkeiten, die Person zu wählen, die seine Jacke zurückbekommt, $\binom{7}{2}$ Möglichkeiten, die beiden Personen auszuwählen, die ihre Jacke zurückbekommen, und so weiter?

Wenn dies wahr ist, wäre der 6-Personen-Fall nur = 1? Denn obwohl dieses Muster nahelegt$\binom{7}{6}\cdot 1$Möglichkeiten, genau 6 Personen mit den richtigen Jacken zu haben, kann ich nicht sehen, wie dies möglich sein könnte. Wenn jeder außer 1 die richtige Jacke hat, muss die letzte Person auch die richtige Jacke haben. Nach dieser Logik sollte die Antwort lauten

$$ = 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$$

Bitte lassen Sie mich wissen, wenn ich irgendwo einen Fehler gemacht habe, jeder Rat wäre dankbar!

Answer 1

Eine Permutation von $n$Objekte, bei denen kein Objekt an seiner ursprünglichen Position verbleibt, werden als Störung bezeichnet . Sie fragen also nach der Anzahl der Störungen von sieben Objekten, dh der$7$-th Störung Nummer, die ist $1854$.

Ihr Ansatz, diese Zahl durch Einschluss / Ausschluss zu berechnen, ist gut. Ihr erstes Argument ist jedoch falsch. Sie zählen in der Tat die Zahlen sehr falsch$A_i$. Wie Sie später bemerken, ist es beispielsweise für genau sechs Personen unmöglich , ihre eigene Jacke zurückzubekommen. Immerhin muss die einzige verbleibende Person dann die einzige verbleibende Jacke bekommen, die dann auch korrekt sein muss.

Für ein anderes Beispiel die Anzahl der Möglichkeiten mindestens $5$ Leute können ihre eigene Jacke bekommen $$1+\tbinom{7}{5}=22.$$Schließlich bekommt entweder jeder seine eigene Jacke zurück oder genau $5$ Leute bekommen ihre eigene Jacke zurück.

Ihr zweites Argument beginnt in die richtige Richtung. Aber es ist mir völlig unklar, wie Sie dazu kommen:

Nach dieser Logik sollte die Antwort lauten $$= 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.$$

Die herausspringende Zahl ist korrekt, aber das Argument fehlt.