Permutation ohne Wiederholung

Wie viele verschiedene Wörter können wir bilden, indem die Buchstaben in einem Wort umgeordnet werden? Die Wörter selbst müssen keinen Sinn ergeben. Wir werden sehen, dass diese Anzahl mit der Fakultät zu tun hat.

Example 1

Aus dem Wort TEA lassen sich durch umordnen sechs Wörter bilden. Welche?

Solution

TEA, TAE, ETA, EAT, AET, ATE

Das Umformen eines Wortes wird Permutation genennt. Genauer:

Definition 1

Gegeben sein ein Wort mit nn Buchstaben. Eine Permutation des Wortes ist ein Wort das durch umordnen der Buchstaben erhalten wird (vom latainischen permutare, vertauschen). Sind alle Buchstaben im Wort verschieden, so sagen wir auch Permutation ohne Wiederholung.

Das folgende Theorem zeigt, wie die Anzahl Permuationen berechnet werden können.

Theorem 1

Falls ein Wort aus nn Buchstaben besteht, und alle nn Buchstaben im Wort verschieden sind, so gibt es

n!n!

mögliche Wörter, die durch umordnen der Buchstaben gebildet werden können.

Die Formel ist relativ einfach nachzuvollziehen, siehe das Beispiel unten.

Exercise 1

Begründe, warum die Anzahl Permutationen des Wortes ABER gegeben ist durch

4!=4⋅3⋅2⋅1=244!=4\cdot 3\cdot 2\cdot 1=24

sein muss.

Solution

Denken wir uns das Ganze als Selektionsproblem. Wir selektieren einen Buchstaben nach dem anderen vom Wort, und bilden so ein neues Work.

Wir ziehen den ersten Buchstaben, dafür gibt es 44 Möglichkeiten. Dann ziehen wir den zweiten Buchstaben, dafür gibt es je 33 Möglichkeiten, also schon

4⋅3=124\cdot 3=12

Möglichkeiten. Dann ziehen wir den 3. Buchstaben, dafür gibt es noch je 22 Möglichkeite, also schon insgesamt

12⋅2=2412\cdot 2=24

oder

4⋅3⋅2=244\cdot 3\cdot 2 =24

Möglichkeiten. Für den Letzen Buchstaben gibt es noch je eine Möglichkeit, also ingesamt

4⋅3⋅2⋅1=244\cdot 3\cdot 2\cdot 1 =24

Möglichkeiten. Der ganzer Prozess lässt sich gut mit einem Baum darstellen:

Die Aufgabe oben kann leicht mit einem Baum gelöst werden. Bäume spielen eine wichtige Rolle beim Zählen von Wortanordnungen. Hier sind noch ein paar weitere Beispiele, die relative einfach mit Hilfe eines Baums gelöst werden können.

Exercise 2: Bäume 1: Ziehung ohne Zurücklegen

Fünf Kugeln sind mit den Zahlen 11, 33, 55, 77 und 99 beschriftet und in eine Tasche gesteckt. Die Fünf Kugeln werden der Reihe nach gezogen, und auf dem Tisch aufgereiht, um eine neue Zahl zu bilden.

  1. Wie viele mögliche Zahlen können gebildet werden?

  2. Wie viele Zahlen mit Anfangszahl 11 können gebildet werden?

  3. Wie viele Zahlen mit Anfangszahl 55 oder 77 können gebildet werden?

Solution
  1. 5!=5⋅4⋅3⋅2⋅1=120‾5!=5\cdot 4\cdot 3\cdot 2\cdot 1=\underline{120}.
  2. 4!=24‾4!=\underline{24}
  3. 2⋅4!=48‾2\cdot 4! = \underline{48}
Exercise 3: Baume 2: Ziehung ohne Zurücklegen

Fünf Kugeln sind mit den Zahlen 11, 33, 55, 77 und 99 beschriftet und in eine Tasche gesteckt. Drei Kugeln werden der Reihe nach gezogen, und auf dem Tisch aufgereiht, um eine neue Zahl zu bilden. Wie viele mögliche Zahlen können gebildet werden?

Solution

5⋅4⋅3=60‾5\cdot 4\cdot 3=\underline{60}.

Exercise 4: Baum 3: Ziehung mit Zurücklegen

Fünf Kugeln sind mit den Zahlen 11, 33, 55, 77 und 99 beschriftet und in eine Tasche gesteckt. Drei Kugeln werden der Reihe nach gezogen, wobei die Zahlen der Reihe nach auf einem Zettel aufgeschrieben werden. Die Kugel wird vor jeder Ziehung wieder zurückgelegt. Wie viele mögliche Zahlen können gebildet werden?

Solution

5⋅5⋅5=53=125‾5\cdot 5\cdot 5=5^3=\underline{125}.