Derangement Subfaktorielle Rechner

Willkommen beim Derangement (Subfaktorielle) Rechner, einem umfassenden Kombinatorik-Tool, das die Anzahl der Derangements für jede beliebige Menge von n Elementen berechnet. Ein Derangement ist eine Permutation, bei der kein Element an seiner ursprünglichen Position erscheint, bezeichnet als !n oder D(n). Egal, ob Sie Kombinatorik studieren, das klassische Garderobenproblem lösen oder die Wahrscheinlichkeitstheorie erkunden, dieser Rechner bietet detaillierte Schritt-für-Schritt-Lösungen mit interaktiven Visualisierungen.

Was ist ein Derangement?

Ein Derangement (auch Subfaktorielle genannt) ist eine Permutation von Elementen einer Menge, bei der kein Element an seiner ursprünglichen Position erscheint. Die Anzahl der Derangements von n Elementen wird als !n (mit dem Ausrufezeichen vor dem n) oder D(n) geschrieben.

Betrachten wir zum Beispiel drei Elemente an den Positionen {1, 2, 3}. Es gibt insgesamt 3! = 6 Permutationen, aber nur 2 davon sind Derangements:

• (2, 3, 1) — Element 1 geht auf Position 2, Element 2 auf Position 3, Element 3 auf Position 1
• (3, 1, 2) — Element 1 geht auf Position 3, Element 2 auf Position 1, Element 3 auf Position 2

Somit gilt !3 = 2.

Derangement-Formeln

Inklusions-Exklusions-Formel

Die grundlegendste Formel leitet sich aus dem Inklusions-Exklusions-Prinzip ab:

Rekursive Formel

Derangements können auch rekursiv berechnet werden:

mit den Basisfällen: !0 = 1, !1 = 0.

Formel der nächsten Ganzzahl

Für \(n \geq 1\) entspricht die Subfaktorielle der nächstgelegenen Ganzzahl zu \(n!/e\):

Das Garderobenproblem

Die bekannteste Anwendung von Derangements ist das Garderobenproblem (problème des rencontres): Wenn n Gäste ihre Hüte abgeben und die Hüte zufällig zurückgegeben werden, wie hoch ist die Wahrscheinlichkeit, dass kein Gast seinen eigenen Hut zurückerhält?

Die Antwort lautet \(!n / n!\), was bemerkenswert schnell gegen \(1/e \approx 0,3679\) konvergiert. Das bedeutet, dass etwa 36,8 % aller Zufallspermutationen Derangements sind, unabhängig davon, wie viele Elemente vorhanden sind.

So verwenden Sie diesen Rechner

1. n eingeben: Geben Sie die Anzahl der Elemente ein (0 bis 170). Verwenden Sie die Beispiel-Schaltflächen für gängige Werte.
2. Berechnen: Klicken Sie auf "!n berechnen", um die Derangement-Zahl zu ermitteln.
3. Ergebnisse prüfen: Sehen Sie !n, n!, die Derangement-Wahrscheinlichkeit und das Verhältnis zu 1/e.
4. Animation erkunden: Interagieren Sie bei kleinen n mit der visuellen Animation, um zu sehen, wie Derangements funktionieren.
5. Schritte studieren: Untersuchen Sie die detaillierte Inklusions-Exklusions-Aufschlüsselung und die Derangement-Tabelle.

Die ersten 15 Derangement-Zahlen

Anwendungen von Derangements

Wichteln / Secret Santa

Beim Organisieren eines Wichtel-Geschenkaustauschs zieht jeder Teilnehmer einen Namen. Eine erfolgreiche Ziehung, bei der niemand seinen eigenen Namen zieht, ist ein Derangement. Für eine Gruppe von 10 Personen gibt es 1.334.961 gültige Anordnungen von insgesamt 3.628.800 Möglichkeiten.

Kryptographie und Codierungstheorie

Derangements tauchen bei der Analyse von Substitutionschiffren und fehlerkorrigierenden Codes auf. Das Konzept des "keinen Fixpunkts" ist grundlegend für das Verständnis der Stärke von Verschlüsselungen und permutationsbasierter Kryptographie.

Kartenspielen und Mischen

In Kartenspielen messen Derangements die Wahrscheinlichkeit, dass keine Karte nach dem Mischen an ihre ursprüngliche Position zurückkehrt. Dies ist nützlich bei der Analyse der Mischqualität und der Fairness von Spielen.

Wahrscheinlichkeitstheorie

Derangements bieten ein elegantes Beispiel für das Inklusions-Exklusions-Prinzip und veranschaulichen, wie Wahrscheinlichkeiten gegen einfache Grenzwerte konvergieren (in diesem Fall 1/e).

Wichtige Eigenschaften

• Das Verhältnis \(!n/n!\) konvergiert gegen \(1/e \approx 0,367879\), wenn \(n \to \infty\)
• Die Konvergenz ist extrem schnell – bereits bei n = 10 auf 6 Dezimalstellen genau
• \(!n\) erfüllt die Rekurrenz: \(!n = n \cdot !(n-1) + (-1)^n\)
• Die exponentielle Erzeugungsfunktion ist \(e^{-x}/(1-x)\)
• \(!0 = 1\) (die leere Permutation ist definitionsgemäß ein Derangement)

Häufig gestellte Fragen (FAQ)

Was ist ein Derangement?

Ein Derangement ist eine Permutation einer Menge, bei der kein Element an seiner ursprünglichen Position erscheint. Wenn beispielsweise Elemente als {1, 2, 3} bezeichnet werden, ist die Permutation (2, 3, 1) ein Derangement, da kein Element an seinem ursprünglichen Platz steht. Die Anzahl der Derangements von n Elementen wird als !n (Subfaktorielle n) bezeichnet.

Wie lautet die Formel für die Subfaktorielle !n?

Die Subfaktorielle !n kann mit der Inklusions-Exklusions-Formel berechnet werden: \(!n = n! \times \sum_{k=0}^{n} (-1)^k / k!\). Sie kann auch rekursiv berechnet werden: \(!n = (n-1)(!(n-1) + !(n-2))\), mit !0 = 1 und !1 = 0. Eine weitere nützliche Formel ist \(!n = \text{round}(n! / e)\) für \(n \geq 1\).

Wie hoch ist die Wahrscheinlichkeit, dass eine zufällige Permutation ein Derangement ist?

Die Wahrscheinlichkeit, dass eine zufällige Permutation von n Elementen ein Derangement ist, nähert sich mit zunehmendem n dem Wert \(1/e \approx 0,3679\) an. Selbst für kleine n ist diese Näherung bemerkenswert genau. Für n = 5 beträgt die exakte Wahrscheinlichkeit 44/120 ≈ 0,3667, was bereits sehr nah an 1/e liegt.

Was ist das Garderobenproblem?

Das Garderobenproblem (auch bekannt als Problème des Rencontres) ist ein klassisches Wahrscheinlichkeitsrätsel: Wenn n Personen ihre Hüte in einem Restaurant abgeben und die Hüte zufällig zurückgegeben werden, wie hoch ist die Wahrscheinlichkeit, dass niemand seinen eigenen Hut zurückerhält? Die Antwort ist die Anzahl der Derangements !n geteilt durch die Gesamtzahl der Permutationen n!, was sich \(1/e \approx 36,79\%\) nähert.

Wie ist das Verhältnis zwischen Derangements und der Fakultät?

Derangements (!n) und Fakultäten (n!) sind eng miteinander verwandt: \(!n = n! \times \sum(-1)^k/k!\) für k von 0 bis n. Das Verhältnis !n/n! ergibt die Wahrscheinlichkeit eines Derangements, die gegen 1/e konvergiert. Außerdem ist !n die nächstgelegene ganze Zahl zu n!/e für \(n \geq 1\), was n!/e zu einer sehr nützlichen Näherung macht.

Zusätzliche Ressourcen

• Derangement - Wikipedia
• Inklusions-Exklusions-Prinzip - Wikipedia
• OEIS A000166 - Subfaktorielle Sequenz