Kombinatorik – Theorie der Kunst des Zählens

Die Kombinatorik ist die Kunst des Zählens. Mit diesem Teilgebiet der Mathematik können wir die Zahl der möglichen Anordnungen oder Auswahlen von Objekten bestimmen.

Bestimmung der Zahl möglicher Anordnungen oder Auswahlen von
unterscheidbaren oder nicht unterscheidbaren Objekten
mit oder ohne Beachtung der Reihenfolge.

Entscheidungsbaum zur Kombinatorik

kombinatorik 1 meinstein

Permutation

Anzahl Möglichkeiten = n!

mit n: Anzahl Objekte

Typische Aufgaben sind die folgenden:

Ordne die vier Ziffern 1, 2, 3, 4 in allen möglichen Reihenfolgen. Wie viele gibt es?

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2412
2421
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321

Bilde aus den vier Buchstaben ROMA alle möglichen Reihenfolgen. Welche hat eine Bedeutung?

ROMA ORMA MROA AROM
ROAM ORAM MRAO ARMO
RMOA OMRA MORA AORM
RMAO OMAR MOAR AOMR
RAOM OARM MARO AMRO
RAMO OAMR MAOR AMOR

ROMA (Stadt Rom),
RAMO (dat.sing. von ramus = Zweig)
ORAM (acc.sing. von ora = Rand, Grenze)
MORA (Verzögerung, Rast)
MARO (Familienname des Dichters Publius Vergilius Maro)
AMOR (Gott der Liebe)
ARMO (1. Person Präs. Aktiv von armare: ich rüste auf)

Permutation mit einer Wiederholung

Die Anzahl der Permutationen von n Objekten, von denen k identisch und damit nicht unterscheidbar sind, berechnet sich zu

Permutation mit Wiederholung 1

Beispiel: SAAL

Berechne die Anzahl der Anordnungen.

n = 4   Das Wort hat 4 Buchstaben
k = 2   Zwei der Buchstaben (AA) sind identisch

4! / 2! = 24 / 2 = 12 Möglichkeiten

AALS AASL ALAS ALSA ASAL ASLA
LAAS LASA LSAA SAAL SALA SLAA

Permutation mit mehreren Wiederholungen

Gibt es nicht nur eine, sondern s Gruppen, mit jeweils k1,…,ks identischen Objekten, so lautet die Formel

Permutation mit Wiederholung 2

Beispiel: MISSISSIPPI

Auf wie viele Arten kann das Wort Mississippi angeordnet (permutiert) werden?

n = 11    es hat 11 Buchstaben
k1 = 4   Der Buchstabe I kommt 4 mal vor
k2 = 4   Der Buchstabe S kommt 4 mal vor
k3 = 2   Der Buchstabe P kommt 2 mal vor

Es gibt also 34’650 Möglichkeiten, das Wort anzuordnen.

Hier gibt es einen Permutations-Generator.

Variation

Eine Variation oder geordnete Stichprobe ist eine Auswahl von Objekten mit einer bestimmten Reihenfolge.

  • Darf jedes Objekt nur einmal auftreten spricht man von einer Variation ohne Wiederholung.
  • Können Objekte mehrfach ausgewählt werden, so spricht man von einer Variation mit Wiederholung. 

Variation ohne Wiederholung

Mögliche Anordnungen:

Variation ohne Wiederholung

Beispiel: Ziehen von 3 Kugeln aus Urne mit 5 verschiedenen Kugeln

Wenn aus einer Urne mit fünf verschiedenen Kugeln dreimal ohne Zurücklegen gezogen wird, sind 5 ⋅ 4 ⋅ 3 = 60 verschiedene Auswahlen möglich.

Ohne Wiederholung heisst bei der Urne auch: Ohne Zurücklegen.

Variation mit Wiederholung

Mögliche Anordnungen:

nk

Die Ermittlung der Anzahl möglicher Variationen ist eine Standardaufgabe der abzählenden Kombinatorik.

Beispiel: Ziehen von 3 Kugeln mit Zurücklegen aus Urne mit 5 verschiedenen Kugeln

Wenn aus einer Urne mit fünf verschiedenen Kugeln dreimal mit Zurücklegen gezogen wird, dann sind 5 ⋅ 5 ⋅ 5 = 53 = 125 verschiedene Auswahlen möglich

Kombination

Eine Kombination oder ungeordnete Stichprobe ist eine Auswahl von Objekten ohne Reihenfolge.

Bei einer Kombination ohne Wiederholung werden k aus n Objekten ohne Beachtung der Reihenfolge ausgewählt, wobei jedes Objekt nur einmal ausgewählt werden kann.

Kombination ohne Wiederholung

In einer Urne befinden sich fünf verschiedenfarbige Kugeln. Es sollen drei Kugeln ohne Zurücklegen (= ohne Wiederholung) und unter Beachtung der Reihenfolge gezogen werden. Wie viele Möglichkeiten gibt es?

Kombination mit Wiederholung

 

Die Permutation ist eine Anordnung. Es werden alle Elemente der Grundmenge betrachtet.
Die Reihenfolge wird berücksichtigt.

Bei der Variation oder Kombination wird nur eine Auswahl (Stichprobe) der Grundmenge betrachtet.

Bei der Variation wird die Reihenfolge berücksichtigt.

Bei der Kombination wird die Reihenfolge nicht berücksichtigt.