Permutationen mit Wiederholung

Viele Worte bestehen nicht wie eben verlangt aus verschiedenen Buchstaben, sondern einige Buchstaben wiederholen sich, wie bei Lotto, Otter, Otto, Banane, …

Betrachtet man die möglichen Anagramme, so stellt man fest, dass einige Anagramme mehrmals auftauchen. Dies kommt daher, dass z.B. beim Wort Otter das erste t und das zweite t nicht unterschieden werden. Vertauscht man also den zweiten und dritten Buchstaben, entsteht kein neues Anagramm, sondern ein bereits bekanntes.

Bei einem Wort wie Otter mit \(5\) verschiedenen Buchstaben gibt es \(5! = 120\) Möglichkeiten, diese anzuordnen. Die zwei t’s könnte man auf \(2!=2\) Möglichkeiten anordnen. Da sie sich nicht unterscheiden lassen, gibt es also insgesamt nicht \(5!\) sondern nur \(\frac{5!}{2!}=60\) Möglichkeiten.

Betrachtet man den Namen BOB: Wären alle Buchstaben verschieden, gäbe es \(3! = 6\) Permutationen. Hier sind aber zwei Buchstaben gleich, also gibt es nur \(\frac{3!}{2!}=3\) verschiedene Anagramme. Zur Verdeutlichung unterscheiden wir zunächst die beiden B’s: BOB. Hieraus können die Anagramme BOB, BOB, OBB, OBB, BBO und BBO gebildet werden. Offensichtlich sind aber je \(2\) Anagramme identisch und es bleiben: BOB, OBB und BBO.

Man spricht hierbei von einer \(k\)-Permutation aus einer \(n\)-Menge mit Wiederholung (\(k > n\)) . lm Beispiel BOB wäre \(k=3, n=2\).

Hat man jetzt nicht nur einen Buchstaben, der mehrfach vorkommt, sondern mehrere, so muss man natürlich auch hier beachten, dass verschiedene Anagramme zusammenfallen.

Beispiel: MISSISSIPPI

Das Wort besteht aus \(11\) Buchstaben \(\Rightarrow k=11\). Wären diese verschieden, so gäbe es \(11!=39916800\) Möglichkeiten der Anordnung. Hier kommt aber das I viermal, das S viermal und das P zweimal vor. Also gibt es insgesamt \(\frac{11!}{4! \cdot 4! \cdot 2!}=34650\) Anordnungen der Buchstaben.

Es handelt sich bei diesem \(k\)-Tupel also um ein Tupel mit Elementen \(a_i\) aus einer \(n\)-Menge, wobei \(a_i\) genau \(k_i\)-mal vorkommt.

Angewendet auf das Wort MISSISSIPPI gilt:

\(k=11, a_1=M, a_2=I, a_3=S, a_4=P, k_1=1, k_2=4, k_3=4, k_4=2\) und deshalb folgt die obige Formel für die Anzahl der Anagramme.