Permutationen

EINFÜHRUNG IN GEORDNETE ANORDNUNGEN

Permutationen sind ein grundlegendes Konzept in der Kombinatorik, das alle möglichen geordneten Anordnungen der Elemente einer gegebenen Menge beschreibt. Bei Permutationen werden alle Elemente verwendet, und ihre Anordnung ist wichtig. Jede Änderung der Reihenfolge bedeutet eine andere Permutation, was Permutationen von Kombinationen unterscheidet, bei denen die Reihenfolge nicht wichtig ist.

Wenn wir n verschiedene Elemente haben, ist die Anzahl aller möglichen Permutationen dieser Elemente:

P(n) = n! (n Fakultät)
wobei n! = n * (n – 1) * (n – 2) * … * 2 * 1

BEISPIEL 1: GRUNDLEGENDE PERMUTATIONEN

Wie viele verschiedene Anordnungen der Buchstaben A, B und C gibt es?

n = 3 → P(3) = 3! = 3 * 2 * 1 = 6

Permutationen: ABC, ACB, BAC, BCA, CAB, CBA

PERMUTATIONEN MIT GLEICHEN ELEMENTEN (MIT WIEDERHOLUNG)

Wenn wir in einer Menge sich wiederholende (gleiche) Elemente haben, dann erzeugt nicht jeder Austausch gleicher Elemente eine neue, unterscheidbare Permutation. In diesem Fall wird die Anzahl der Permutationen reduziert, indem durch die Fakultäten der Anzahl der Wiederholungen jedes Elements geteilt wird:

Wenn wir n Elemente haben, von denen:

• r₁ Elemente einer ersten Art gleich sind,
• r₂ Elemente einer zweiten Art gleich sind,
• …,
• rₖ Elemente einer k-ten Art gleich sind,
  dann ist die Anzahl der verschiedenen Permutationen:

P(n; r₁, r₂, …, rₖ) = n! / (r₁! * r₂! * … * rₖ!)

BEISPIEL 2: PERMUTATIONEN MIT GLEICHEN ELEMENTEN

Wie viele verschiedene Permutationen hat das Wort MAMA?

Buchstaben: M – 2×, A – 2× → n = 4 (Gesamtzahl der Buchstaben), r₁ = 2 (Anzahl der Ms), r₂ = 2 (Anzahl der As)

P = 4! / (2! * 2!) = (4 * 3 * 2 * 1) / ((2 * 1) * (2 * 1)) = 24 / (2 * 2) = 24 / 4 = 6

Permutationen: MAMA, MAAM, MMAA, AMAM, AMMA, AAMM

ZYKLISCHE PERMUTATIONEN

Wenn Elemente im Kreis angeordnet werden, sprechen wir von zyklischen (oder zirkulären) Permutationen. Bei einer kreisförmigen Anordnung gelten Rotationen derselben Anordnung nicht als neue Permutationen.

Für n verschiedene Elemente im Kreis ist die Anzahl der zyklischen Permutationen:

P_Kreis(n) = (n – 1)!

Beispiel: Anordnung von 5 Personen um einen runden Tisch → (5 – 1)! = 4! = 4 * 3 * 2 * 1 = 24 Möglichkeiten.

VERBINDUNG ZU VARIATIONEN UND KOMBINATIONEN

• PERMUTATIONEN: Alle Elemente werden verwendet, die Reihenfolge ist wichtig.
• VARIATIONEN: Eine Teilmenge der Elemente wird verwendet, die Reihenfolge ist wichtig.
• KOMBINATIONEN: Eine Teilmenge der Elemente wird verwendet, die Reihenfolge ist nicht wichtig.

ANWENDUNG VON PERMUTATIONEN

Permutationen werden verwendet bei:

• DER ANORDNUNG VON PERSONEN, GEGENSTÄNDEN, ZEICHEN
• DER KODIERUNG UND ERSTELLUNG VON PASSWÖRTERN
• DEM UMSTELLEN VON ELEMENTEN OHNE WIEDERHOLUNG
• DER LÖSUNG VON PROBLEMEN IN DER SPIELTHEORIE UND OPTIMIERUNG

FAZIT

Permutationen stellen alle möglichen Arten der Anordnung von Elementen dar, bei denen die Reihenfolge entscheidend ist. Die Anzahl der Permutationen wächst schnell mit der Anzahl der Elemente, insbesondere wenn es keine Wiederholungen gibt. Das Verständnis der grundlegenden und speziellen Formen von Permutationen ist wesentlich für die effektive Lösung kombinatorischer Probleme.