Permutation mit Wiederholung

Was wenn einige Buchstaben im Wort identisch sind? Wie viele Wörter können dann geformt werden durch Umordnen der Buchstaben?

Example 1

Finde alle möglichen Wörter von TEE durch Umordnen der Buchstaben. Wie viele gibt es?

Solution

TEE, ETE, EET

Beide Wörter TEA (vom letzten Kapitel) und TEE haben gleich viele Buchstaben, aber da TEE identische Buchstaben besitzt, können weniger Wörter damit gebildet werden. Wir nennen dies immer noch eine Permutation, oder genauer:

Definition 1

Das Umordnen der Buchstaben in einem Wort in dem einige Buchstaben identisch sind, wird Permutation mit Wiederholung genannt.

Die Anzahl Permutationen lassen sich ebenfalls mit einer Formel berechnen. Wir nennen diese (informell) Formel die MISSISSIPPI- Formel (genauer ist es ein Multinomial Koeffizient).

Theorem 1: MISSISSIPPI-Formel

Gegeben ist ein Wort mit nn Buchstaben, wobei einige der Buchstaben identisch sind. Die Anzahl verschiedenen Wörter, die durch umordnen der Buchstaben gebildet werden können ist

n!k1!⋅k2!⋅...⋅kr!\frac{n!}{k_1!\cdot k_2!\cdot ...\cdot k_r!}

wobei rr Buchstaben in mehreren Kopien vorkommen, und k1,...,krk_1, ..., k_r die Anzahl Kopien sind. Konkreter ist die Anzahl Wörter die mit dem Wort MISSISSIPPI begildet werden können

11!4!⋅4!⋅2!\frac{11!}{4!\cdot 4!\cdot 2!}

da es 1111 Buchstaben besitzt, und es 44 S, 44 I, und 2 P besitzt.

Wir teilen also die Anzahl möglicher Wörter die gebildet werden können wenn alle Buchstaben unterschiedlich wären (11!11!) durch die Anzahl der gleichen Buchstaben im Wort, also durch 4!4! (wegen den 44 S), nochmals durch 4!4! (wegen den 44 I) und noch durch 2!2! (wegen den 22 P). Wir "faktorisieren" also die zu vielen Wörter heraus.

Wir werden diese Formel aber nicht weiter beweisen, sie gilt aber allgemein. Hier ist noch ein weiteres Beispiel:

Example 2

Die Anzahl Wörter, die durch herumarrangieren der Buchstaben des Wortes HELLO gebildet werden können ist

5!2!=60\frac{5!}{2!}=60
Exercise 1

  1. Wie viele Wörter können aus dem unten stehenden Wort durch herumarrangieren der Buchstaben gebildet werden?

    1. HIPPOPOTAMUS
    2. WORD
    3. 00011111

  2. Überprüfe die MISSISSIPPI-Formel indem alle Möglichen Wörter aufgeschrieben werden, die aus dem Wort AABB gebildet werden können.

  3. Eine Münze wird 1010-mal geworfen. Wie viele Möglichkeiten gibt es, genau 44-Kopf und 66-mal Zahl zu werfen (beliebige Reihenfolge).

Solution
    1. 12!3!⋅2!=39 916 800\frac{12!}{3!\cdot 2!}=39\,916\,800
    2. 4!=244!=24
    3. 8!3!⋅5!=56\frac{8!}{3!\cdot 5!}=56
  2. Selber machen
  3. Also, auf wie viele Arten können wir das Wort KKKKZZZZZZ permutieren? Es ist 10!4!⋅6!=210\frac{10!}{4!\cdot 6!}=210