Fixpunktfreie Permutation

Begriff und Wahrscheinlichkeit

Eine fixpunktfreie Permutation, auch Derangement, ist eine Permutation, bei der kein Element seine Ausgangsposition behält. Für die symmetrische Gruppe Sₙ aller Permutationen von {1,…,n} gilt für eine Permutation π: π(i) ≠ i für alle i=1,…,n. Anders gesagt: In ihrer Zyklendarstellung kommt kein Zyklus der Länge eins vor.

Dₙ bezeichnet die Menge der fixpunktfreien Permutationen in Sₙ, dₙ = |Dₙ| ihre Anzahl. Sind alle n! Permutationen gleich wahrscheinlich, ist der Anteil und damit die Wahrscheinlichkeit einer fixpunktfreien Permutation pₙ = |Dₙ| / |Sₙ| = dₙ / n!.

Das Konzept lässt sich auf jede endliche Menge anwenden, etwa auf Buchstaben eines Alphabets; für Berechnungen genügt meist die Menge {1,…,n}.

Ausgangsproblem und Anschauung

Fixpunktfreie Permutationen beschreiben mehrere gleichartige Zufallsprobleme. Beim Treize-Spiel werden 13 gemischte Karten einer Farbe nacheinander aufgedeckt und zugleich As, Zwei, …, König aufgerufen. Der Spieler gewinnt, wenn mindestens einmal aufgerufene und aufgedeckte Karte übereinstimmen. Er verliert genau dann, wenn keine Karte an ihrer ursprünglichen Position erscheint, also bei einem Derangement.

Dasselbe gilt für das Hüteproblem: n Gäste erhalten zufällig Hüte zurück. Die Wahrscheinlichkeit, dass mindestens ein Gast seinen eigenen Hut bekommt, ist die Gegenwahrscheinlichkeit zu einer fixpunktfreien Permutation. Pierre Rémond de Montmort gab für Treize die Gewinnwahrscheinlichkeit nahe bei 1 − e⁻¹ ≈ 0,6321 an. Auch Eulers Rencontre-Spiel führt auf dieselbe mathematische Fragestellung.

Anzahl und Grenzwert

Die Zahl der fixpunktfreien Permutationen heißt Subfakultät und lautet !n = dₙ = n! · Σₖ₌₀ⁿ ((−1)ᵏ / k!). Daraus folgt für ihren Anteil pₙ = !n / n! = Σₖ₌₀ⁿ ((−1)ᵏ / k!).

Wichtige Anfangswerte sind d₀ = 1, d₁ = 0, d₂ = 1, d₃ = 2, d₄ = 9, d₅ = 44 und d₆ = 265. Beispielsweise sind von 24 Permutationen von vier Elementen 9 fixpunktfrei; ihr Anteil beträgt 0,375. Für n ≥ 4 liegt der Anteil bei ungefähr 37 % und wird daher auch 37-%-Regel genannt.

Genauer gilt |pₙ − e⁻¹| < 1/(n+1)!. Daher ist limₙ→∞ pₙ = e⁻¹ = 0,3678794… . Außerdem gilt für n ≥ 1: dₙ = [n! / e], wobei [·] die übliche Rundung auf ganze Zahlen bezeichnet.

Zwei Herleitungen

Mit dem Inklusions-Exklusions-Prinzip setzt man Aᵢ = {π ∈ Sₙ | π(i) = i}. Dann sind die fixpunktfreien Permutationen genau Dₙ = Sₙ \ (A₁ ∪ … ∪ Aₙ). Für k festgelegte Fixpunkte bleiben (n−k)! Möglichkeiten für die übrigen Elemente. Da k Fixpunkte auf (n über k) Arten ausgewählt werden können, ergibt sich |A₁ ∪ … ∪ Aₙ| = Σₖ₌₁ⁿ (−1)ᵏ⁻¹ (n über k)(n−k)! = Σₖ₌₁ⁿ (−1)ᵏ⁻¹ n!/k!. Nach Abzug von n! entsteht die Summenformel für dₙ.

Eine zweite Herleitung verwendet Rekurrenzen. Für π(1)=j gibt es zwei Fälle: Entweder π(j)=1; dann verbleiben dₙ₋₂ Möglichkeiten. Oder 1 steht nicht an der Stelle j; dann gibt es dₙ₋₁ Möglichkeiten. Weil j n−1 mögliche Werte hat, gilt dₙ = (n−1)(dₙ₋₁ + dₙ₋₂) mit d₁ = 0 und d₂ = 1. Umgeformt folgt auch dₙ = n dₙ₋₁ + (−1)ⁿ.

Partielle Derangements und Anwendungen

Bei einem partiellen Derangement bleiben genau k Elemente an ihrem Platz. Die Menge solcher Permutationen heißt Dₙ,ₖ, ihre Anzahl dₙ,ₖ Rencontres-Zahl. Sie ist dₙ,ₖ = !(n−k) · (n über k) = n!/k! · Σᵢ₌₀ⁿ⁻ᵏ ((−1)ⁱ / i!). Für k = 0 erhält man wieder die fixpunktfreien Permutationen: Dₙ = Dₙ,₀ und dₙ = dₙ,₀. In S₃ gibt es beispielsweise drei Permutationen mit genau einem Fixpunkt.

Bei der ENIGMA führte die Konstruktion fixpunktfreie und selbstinverse Permutationen aus: Ein Buchstabe konnte nicht in sich selbst verschlüsselt werden. Das vereinfachte Verschlüsselung und Entschlüsselung, bedeutete aber zugleich eine signifikante kryptographische Schwächung. Auch Wichteln lässt sich als fixpunktfreie Permutation der beteiligten Personen modellieren, wenn niemand sich selbst beschenkt.