Suchfunktion


 
 

Navigation

Trainingsaufgaben Mathe

bedingte Wahrscheinlichkeit
Experimenttypen
Häufigkeit
Zufallsexperiment

Inhaltsverzeichnis
Mathematik

Startseite

Permutationen - Grundlagen der Kombinatorik


 

Allgemeines über Experimenttypen in der Wahrscheinlichkeitsrechnung (Stochastik):

Es gibt in der Wahrscheinlichkeitsrechnung zwei Experimenttypen, die einem immer wieder begegnen. Das sind einerseits Laplace-Experimente (alle Ereignisse sind gleich wahrscheinlich) und auf der anderen Seite Bernoulli- Experimente (genau zwei Elemente in der Ergebnismenge).

In diesem Kapitel befassen wir uns nun, welche Bedeutung die Reihenfolge der Elemente für die Wahrscheinlichkeit eines Gesamtergebnisses hat. Mit dieser Thematik befasst sich die Kombinatorik, also wie sich die Anordnung bzw. Wahrscheinlichkeit von Elementen sich ändert, wenn die Reihenfolge berücksichtigt wird.

Grundlagen der Kombinatorik - Permutationen

Wie eingangs erwähnt, müssen in der Stochastik bzw. der sogenannten Kombinatorik die Anzahl der Möglichkeiten berechnet werden, bestimmte Elemente in einer Reihenfolge zu ordnen. Diese Anordnung von Elementen in einer bestimmten Reihenfolge wird in der Kombinatorik als Permutation bezeichnet. Dabei unterscheidet man zwei Arten von Permutationen, sind die Elemente unterscheidbar (ohne Wiederholung) oder sind die Elemente nicht unterscheidbar, d.h. ein Element kann in der Anordnung mehrfach vorkommen (mit Wiederholung)

Zur Wiederholung: In einem anderen Kapitel haben wir uns mit der Variation befasst, im Unterschied zur Variation werden alle Elemente ausgewählt (n-Elemente und n-Auswahlen bei der Permutation bzw. n-Elemente und k-Auswahlen bei der Variation)

Permutation ohne Wiederholung:

Um die Permutation anschaulich darzustellen, beginnen wir mit einem Experiment: Wir haben vier Kugeln. Auf wie viele verschiedene Arten lassen sich die schwarze,  rote,  blaue und weißer Kugel in einer Reihe hintereinander legen?

Wir haben in diesem Fall ein Experiment, indem jedes Element (bzw. Kugel) nur einmal vorkommen darf. Zu Beginn haben wir 4 Kugeln vorliegen, daher kann man an erster Stelle (in der Reihe) 4 Kugeln auslegen. Wir haben also 4 Möglichkeiten, die erste Stelle zu besetzen. Für die zweite Position in der Reihe haben wir nur noch 3 Kugeln zur Verfügung. Wir haben also nur noch 3 Möglichkeiten, die zweite Stelle zu besetzen. Für die dritte Position haben wir noch 2 Kugeln zur Verfügung (als noch 2 Möglichkeiten). Für die vierte Position in der Reihe haben wir nur noch 1 Kugel übrig, also auch nur noch 1 Möglichkeit, eine Kugel auszulegen.

Nun müssen wir nur noch die Gesamtanzahl bestimmen: an erster Stelle haben wir 4 Möglichkeiten, an zweiter Stelle 3, an zweiter Stelle 2, an dritter Stelle 1 Möglichkeit, ergibt zusammen: 4 · 3 · 2 · 1 = 24 Möglichkeiten.


Nun wollen wir uns die Formel für die Möglichkeiten bei einer Aneinanderreihung von n-Permutationen ermitteln:

Wie im Beispiel der Kugeln gezeigt, gibt es bei der ersten Stelle n Möglichkeiten (aus n Elementen), da noch kein Element verwendet wurden. Nachdem die erste Stelle in der Anordnung der Ereignisse besetzt ist, bleiben noch (n-1) Elemente übrig, die für die zweite Stelle verwendet werden können. Also haben wir an zweiter Stelle der Anordnung noch (n - 1) Möglichkeiten ein Element zu positionieren.

Damit erhalten wir bei n-Permutationen (Anordnungen mit Berücksichtigung der Reihenfolge und ohne Wiederholung der Elemente) folgende Möglichkeiten der Anordnung der Elemente:

      Möglichkeiten = n · (n -1) · (n - 2) · (n - 3)  · .... ·1  = n!


Permutation mit Wiederholung

Manchmal liegen auch Permutationen vor, bei denen die Elemente teilweise oder gar nicht unterscheidbar sind oder das grundsätzlich bei den Experimenten Wiederholungen zulässig sind. Auch in diesem Fall können wir die Anzahl der Möglichkeiten berechnen, die Elemente in einer Reihenfolge ohne Wiederholung zu verwenden:

Ohne eine lange Herleitung: Sind k Elemente von den insgesamt n Elementen nicht unterscheidbar, so muss diese in der Anzahl der Möglichkeiten berücksichtigt werden. Daher muss die obige Formel "Permutationen bei unterscheidbaren Elementen" noch durch die Anzahl der nicht unterscheidbaren Elementen geteilt werden. Als Formel für die Permutation von n Elementen mit k Elementen, die nicht unterscheidbar sind, gilt:

Möglichkeiten  = n! : k!

Beispiel: Wir haben zwei grüne Kugeln (g) und eine rote Kugel (r). Wie viele Möglichkeiten gibt es, diese auszulegen (in Reihenfolge)?

  • 1. Schritt: Bestimmung von n: wir haben 3 Objekte (n = 3)
  • 2. Schritt: Bestimmung von k: wir haben 2 nicht unterscheidbare Objekte (k = 2)
  • 3. Schritt: Einsetzen in die Formel: 3! : 2! = 3, wir haben also drei Möglichkeiten
  • "manuelle" Überprüfung: ggr, grg, rgg (3 Möglichkeiten)



Zusammenfassung der Kombinatorik

Die Kombinatorik befasst sich mit der Anzahl von Anordnung von einer bestimmten Anzahl an Elementen mit oder ohne Berücksichtigung der Reihenfolge. Sind die Elemente unterscheidbar (und kommen diese nur einzeln vor) so spricht man von "ohne Wiederholung". Sind die Elemente hingegen nicht unterscheidbar, so spricht man von "mit Wiederholung", da jedes Element, dass bereits verwendet wurde, wieder verwendet werden kann.


  • Kombination (mit Wiederholung) - Auswahl von k aus n Elementen - keine Reihenfolgenbeachtung Kombination mit Wiederholung
  • Kombination (ohne Wiederholung) - Auswahl von k aus n Elementen - keine ReihenfolgenbeachtungKombination ohne Wiederholung
  • Variation (mit Wiederholung) - Auswahl von k aus n Elementen - Reihenfolgenbeachtung:                                   nk
  • Variation (ohne Wiederholung) - Auswahl von k aus n Elementen - Reihenfolgenbeachtung:            Variation ohne Wiederholung

  • Permuation (mit Wiederholung) - Auswahl von n aus n Elementen - Reihenfolgenbeachtung:               Permutation mit Wiederholung


  • Permutation (ohne Wiederholung) - Auswahl von n aus n Elementen - Reihendolgenbeachtung:                               n!