Einführung in die Kombinatorik

 "Wie viele Möglichkeiten gibt es...

• ...3 Objekte in verschiedenen Reihenfolgen anzuordnen?"
• ...2 Objekte aus einer Menge von 4 Objekten auszuwählen?"

• ...n Objekte in verschiedenen Reihenfolgen anzuordnen?"
• ...k Objekte aus einer Menge von n Objekten auszuwählen?"

Permutationen

Versuchen Sie andere Beispiele und kontrollieren Sie Ihr Ergebnis:

Auswahl von k aus n möglichen Elementen

 Dabei müssen wir 4 Fälle unterscheiden:
  

Wenn die Reihenfolge der ausgewählten Elemente berücksichtigt wird, spricht man von Variationen, sonst von Kombinationen.

Testen Sie andere Beispiele und kontrollieren Sie Ihre Lösung:

Zur allgemeinen Lösung für

• mit Reihenfolge mit Wiederholung bzw. Variationen mit Wiederholung
• mit Reihenfolge ohne Wiederholung bzw. Variationen ohne Wiederholung
• ohne Reihenfolge mit Wiederholung bzw. Kombinationen mit Wiederholung
• ohne Reihenfolge ohne Wiederholung  bzw. Kombinationen ohne Wiederholung

Permutationen von n Objekten

• Beispiel n=3:Wir haben 3 verschiedene Objekte. Wie viele verschiedene Reihenfolgen gibt es, diese Objekte anzuordnen ?

Die Objekte seine die Zahlen 1,2,3. Dann gibt es für das erste Objekt 3 Möglichkeiten, für das zweite Objekt gibt es noch jeweils 2 Möglichkeiten, für das dritte Objekt gibt es jeweils nur noch eine Möglichkeit. Insgesamt haben wir

3! = 3·2·1 = 6 Möglichkeiten:
123, 132, 213, 231, 312, 321
• Allgemeiner Fall: Wir haben n verschiedene Objekte. Wie viele verschiedene Reihenfolgen gibt es, diese Objekte anzuordnen ?

Die Objekte seine die Zahlen 1,2,3,...n. Dann gibt es für das erste Objekt n Möglichkeiten, für das zweite Objekt gibt es noch jeweils n-1 Möglichkeiten, für das dritte Objekt gibt es jeweils noch (n-2) Möglichkeiten, für das letzte (n-te) Objekt nur noch eine Möglichkeit. Insgesamt haben wir

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

Auswahl von k Objekten aus einer Menge mit n Objekten

• mit Reihenfolge mit Wiederholung (Variationen mit Wiederholung):
• Beispiel: Auswahl von k=2 Objekten aus einer Menge mit n=4 Objekten mit Wiederholung und mit Berücksichtigung der Reihenfolge.

Für das erste Objekt können wir aus 4 Möglichkeiten wählen, für das zweite auch. Insgesamt sind es 4·4 = 16 Möglichkeiten:
11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44
• Allgemeiner Fall: Auswahl von k Objekten aus einer Menge mit n Objekten mit Wiederholung und mit Berücksichtigung der Reihenfolge.

Für das erste Objekt können wir aus n Möglichkeiten wählen, für das zweite auch, für die folgenden ebenso. Insgesamt sind es k Wahlen, die wir treffen Die Möglichkeiten ergeben sich also dadurch, dass wir die Zahl n k-mal mit sich selbst multiplizieren: n^k Möglichkeiten.
• mit Reihenfolge ohne Wiederholung (Variationen ohne Wiederholung):
• Beispiel: Auswahl von k=2 Objekten aus einer Menge mit n=4 Objekten ohne Wiederholung und mit Berücksichtigung der Reihenfolge.

Für das erste Objekt können wir aus 4 Möglichkeiten wählen, für das zweite bleiben nur nach 3. Insgesamt sind es 4·3 = 12 Möglichkeiten:
12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43
• Allgemeiner Fall: Auswahl von k Objekten aus einer Menge mit n Objekten ohne Wiederholung und mit Berücksichtigung der Reihenfolge.

Für das erste Objekt können wir aus n Möglichkeiten wählen, für das zweite nur nach (n-1), für die folgenden jeweils eines weniger. Insgesamt sind es k Wahlen, die wir treffen Die Möglichkeiten ergeben sich also zu: n·(n-1)·(n-2)·...·(n-k+1) = n! / (n-k)! Möglichkeiten.
• ohne Reihenfolge ohne Wiederholung (Kombinationen ohne Wiederholung):
• Beispiel: Auswahl von k=2 Objekten aus einer Menge mit n=4 Objekten ohne Wiederholung und ohne Berücksichtigung der Reihenfolge.

Mit Reihenfolge ergaben sich 12 Möglichkeiten, nämlich 12, 13, 14, 21, 23, 24, 31, 32, 34, 41, 42, 43. Jetzt identifizieren wir Elemente, die durch Vertauschungen zwischen den 2 Objekten entstehen, also 12 = 21, 23 = 32,... . Bei k=2 stelligen Elementen gibt es zu jedem 2·1 = 2! Elemente, die wir nun als identisch ansehen. Es bleiben also nur noch 12:2= 6 Möglichkeiten: 12, 13, 14, 23, 24, 34
• Allgemeiner Fall: Auswahl von k Objekten aus einer Menge mit n Objekten ohne Wiederholung und ohne Berücksichtigung der Reihenfolge.

Mit Reihenfolge ergaben sich n!/(n-k)! Möglichkeiten. Jetzt identifizieren wir Elemente, die durch Vertauschungen zwischen den k ausgewählten Objekten entstehen. Bei k-stelligen Elementen gibt es zu jedem k! Umsortierungen, die wir nun als identisch ansehen. Es bleiben also nur noch



Möglichkeiten.

• ohne Reihenfolge mit Wiederholung (Kombinationen mit Wiederholung):
• Beispiel: Auswahl von k=2 Objekten aus einer Menge mit n=4 Objekten mit Wiederholung und ohne Berücksichtigung der Reihenfolge.

Hier ergab sich: 11, 12, 13, 14, 22, 23, 24, 33, 34, 44 Wir können also annehmen, dass die Zahlen steigend sortiert sind.

 

• Allgemeiner Fall: Auswahl von k Objekten aus einer Menge mit n Objekten mit Wiederholung und ohne Berücksichtigung der Reihenfolge.

Es sollen aus den Zahlen 1,2,3,...,n jeweils k Zahlen ausgewählt werden. Da die Reihenfolge keine Rolle spielt, können wir annehmen, dass die Elemente monoton steigend geordnet sind. Wählt man z.B. n=5 und k = 3, so ist 223 eine mögliche Wahl. Wir erweitern nun die k=3 Positionen durch Hinzufügung von Trennzeichen beim Wechsel zur um 1 höheren Zahl um n - 1 Positionen und stellen eine Zahl durch das # Zeichen dar. Dann erhalten  wir für 223 die Darstellung |##|#|| . (Der vordere Trennstrich bedeutet Übergang von 1 zu 2, die nächsten ## bedeuten dann zweimal die Zahl 2; dann Übergang zur 3. # ist einmal die Zahl 3, und die Trennstriche zum Übergang auf 4 und auf  5 dürfen nicht weggelassen werden.)  Ebenso ist ###|||| = 111, ||||### = 555, ||##||# = 335). Jede ausgewählte Zahl lässt sich also durch Kombination von 3 (im allgemeinen k) # Zeichen und 4 (im allgemeinen n-1) Trennstrichen eindeutig darstellen. Die Aufgabe heißt jetzt: Wähle aus insgesamt k+n-1 Positionen beliebig die Positionen für k Zahlzeichen (#) aus. Dafür gibt es



Möglichkeiten.

Zusammenfassung

Auswahl von k Elementen aus n Elementen
mit Reihenfolge bzw. mit Berücksichtigung der Anordnung		ohne Reihenfolge bzw. ohne Berücksichtigung der Anordnung
Variationen		Kombinationen
mit Wiederholung	ohne Wiederholung	mit Wiederholung	ohne Wiederholung
nk

Übungen

1. Überprüfen Sie die Formeln an Beispielen.
2. Beim Zahlenlotto 6 aus 49 werden 6 Kugeln aus einem Vorrat von 49 Kugeln ohne Zurücklegen gezogen. Wie viele Möglichkeiten für Lottozahlen gibt es ?

Fehler, Anregungen bitte an Thomas Gebhardt