Von Marius Jost
Manche nennen es einfach nur Wahrscheinlichkeitsrechnung, andere erkennen schon etwas genauer: es geht um die abzählende Kombinatorik. Sehr häufig geht es hier um die Frage, wie viele mögliche Anordnungen von z.B. drei verschiedenen Elementen denkbar sind, wenn man alle Elemente auch dabei jeweils verwendet. Sind zum beispiel ein Stern, ein Dreieck und ein Kreis verfügbar, kann man genau 6 verschiedene Anordnungen damit bilden. Das Bild links zeigt dies.
Wer zum Beispiel wissen will, wie viele unterschiedliche Worte man aus dem Wort akutibu bilden kann, oder wer gerade im Gymnasium die 9. Klasse besucht, der sollte ruhig einmal weiter lesen.
Permutationen
Hat man tatsächlich nur 3 verschiedene Elemente (n=3, mehr dazu später) (wie hier der Steren, den Kreis und das Dreieck), dann lässt sich jede mögliche Anordnung dieser wenigen Elemente leicht grafisch darstellen. Sind es aber sehr viel mehr Elemente, dann wird es schon schwieriger, dies in einem Bild zu zeigen. Der Zeitaufwand bei z.B. 6 verschiedenen Elementen wäre schon enorm.
Deshlab müssen wir nun abstrahieren: Welche Formel erklärt die möglichen Anordnungen von n verschiedenen Elementen?
Lösung: Es ist die Formel n! ("n-Fakultät")
Fakultät, das bedeutet, multiplizieren und immer um eins "runter" gehen. Z.B. ist 5!= 5*4*3*2*1
Bei drei verschiedenen Elementen beläuft sich also die Zahl der möglichen Anordnungen (Permutationen) auf 3*2*1 = 6 Möglichkeiten. Warum? Weil für die erste Stelle, die ich mit einem Element besetzen will, drei verschiedene Ausprägungen (Sternchen, Dreieck oder Kreis) verfügbar sind. Für die zweite Stelle gibt es jetzt aber nur noch 2 Elemente, eines hab ich ja schon abgelegt. Für die letzte Stelle bleibt nur noch ein Element übrig: Hier gibt es gar keine Auswahl mehr.
Das hier Dargestellte nennt man Permutation ohne Wiederholung. Hätten wir ein identisches Element, z.B. zwei Sternchen und einen Kreis, spricht man von einer Wiederholung.
Permutationen mit Wiederholungen
Wir schauen uns noch einmal die einfache Permutation ohne Wiederholung an und verändern dann zwei der Elemente so, dass sie nicht zu unterscheiden sind.
Zunächst hier alle möglichen Kombinationen aus einer # einem * und einem + Symbol:
# * +
# + *
+ * #
* + #
* # +
+ # *
Nun überschreiben wir das * und das + einfach mit einem X:
# X X
# X X (identisch)
X X #
X X # (identisch)
X # X
X # X (identisch)
Ist es nicht erstaunlich? Jede zweite Kombination ist identisch. Das heißt, die Zahl der möglichen eindeutigen Anordnungen sinkt auf die Hälfte. Hier ist also jede 2. Anordnung ein Duplikat.
Damit können wir die Zahl eindeutiger Anordnungen bei Wiederholungen berechnen:
Theoretisch mögliche Anordnungen, wenn es keine Widerholungen gäbe geteilt durch die Zahl der Möglichkeiten für die identischen Elemente den Platz zu tauschen.
Stellen wir uns mal vor, wir könnten die beiden X-Symbole unterscheiden. Für die beiden Zeichen (X und X) gibt es 2! Möglichkeiten den Platz zu tauschen, und zwar jedes mal neu. Steht die Raute an erster Stelle wie im Beispiel, kann das erste X links, das zweite X rechts stehen. Die zweite Möglichkeit für die X-Brüder: Das erste X steht rechts und das zweite jetzt links. Auf der ersten Stelle gibt es für die X-Brüder also zwei Möglichkeiten. Ist die erste Stelle besetzt, bleibt nur noch eine Möglichkeit der Besetzung. Also 2*1 = 2!
Die Zahl der möglichen Kombinationen bei Permutationen mit Wiederholung ist also
die Zahl aller theoretisch möglichen Anordnungen, wenn es keine Widerholungen gäbe
__________________________________________________________________________
die Zahl der Möglichkeiten, jeweils den Platz zu tauschen
In diesem Beispiel also:
6*5*4*3*2*1
_______________
2*1
oder allgemein bei k verschiedenen Gruppen
n!
______________
j1! * j2! * .. * jk!
Auf unser Beispiel bezogen gibt es k=2 Gruppen von Objekten, nämlich die erste Gruppe mit den beiden X-Objekten und die zweite Gruppe mit einem einzigen Objekt, dem #-Objekt.
Man muss minutiös unterscheiden, wieviele Gruppen (hierfür steht k) von gleichartigen Objekten es gibt, und man muss wissen, wieviele (hierfür steht j) gleichartige Objekte jeweils in einer Gruppe sind.
Aufgabe und Lösung:
Wie viele Worte lassen sich aus dem Wort akutibu bilden, wenn man nur Kleinbuchstaben nehmen darf und das Wort nicht länger oder kürzer ausfallen darf?
Lösung:
Wir müssen in Ruhe alles auseinander nehmen:
Die erste Frage, die wir beantworten müssen lautet: Wie viele Stellen sind zu besetzen?
Richtig: genau 7. Beweis: a k u t i b u hat _ _ _ _ _ _ _ Stellen, an denen ein Zeichen stehen kann.
n ist also gleich 7 und die theoretisch mögliche Zahl von Kombinationen, die eindeutig sind, wenn es keine Wiederholungen von Buchstaben gäbe, beträgt exakt
n!
also
7!= 7*6*5*4*3*2*1 = 5.040 Möglichkeiten
Allerdings wiederholen sich Bustaben:
In der Schale, wo unsere verstreuten Buchstaben liegen, die aus dem Wort akutibu entnommen sind, finden wir das "u" 2 Mal.
Es gibt folglich 2*1 Möglichkeiten für die beiden u, ihren Platz zu tauschen - und hinterher kann man nicht unterscheiden, welcher der beiden Brüder der nettere oder ältere ist. Beide sehen doch genau gleich aus!
Die Berechnung für die möglichen Kombinationen und damit die Antwort auf die obige Frage lautet also:
n!
__________________ = 5.040 / 2 = 2.520
1!*1!*2!*1!*1!*1!
Im Nenner des Bruches stehen 6 Faktoren, weil es 6 verschiedene Gruppen (oder meinetwegen Klassen) von Objekten gibt. Eine der Klassen, nämlich die, in welcher sich das u als Objekt befindet, hat 2 identische Objekte.
Hier nochnmal die Formel von oben: n steht für die Zahl der Stellen, die wir besetzen. Es ist identisch mit der Gesamtzahl der Zeichen, wie wir zur Verfügung haben (inklusive sich wiederholdene Zeichen). k steht für die Anzahl der Gruppen. Eine Gruppe enthält immer nur eine Art von Objekt (hier: eine Art von Zeichen). Innerhalb einer Gruppe kann sich also ein Symbol wie ein "a" befinden, oder, wie bei unserem Beispiel es gibt innerhalb einer Gruppe j=zwei Mal das "u".
n!
______________
j1! * j2! * .. * jk!
Soweit zum Thema "mögliche Kombinationen bei Permutationen".
Wir haben kurz Permutationen mit und ohne Wiederholungen kennen gelernt. Wenn Du / Sie Fragen haben, einfach mal melden.
Kontakt:
akutibu private Bildung
Marius Jost, Dipl. Int. Betriebswirt
Delkenheimer Str. 18a
65719 Hofheim am Taunus
Telefon: 069 - 17 55 42 10
Sie erreichen uns unter folgender E-Mail Adresse:
info ()at() akutibu.de
069 - 17 55 42 10 - 1
