Kombinatorik (engl.: Combinatorics)

K. bezeichnet – ursprünglich durch Glücksspiele angeregte – Rechenregeln, mit denen die Wahrscheinlichkeit bestimmter Ereigniskombinationen von gleichwahrscheinlichen Elementarereignissen ermittelt wird. Sie ist ein Teilgebiet der Mathematik, das zur Bestimmung der Zahl möglicher Anordnungen oder Auswahlen von unterscheidbaren oder nicht unterscheidbaren Elementen mit oder ohne Beachtung der Reihenfolge herangezogen wird.

Die zwei Grundfragen der Kombinatorik lauten:
Wie viele Möglichkeiten gibt es, n Elemente in verschiedenen Reihenfolgen anzuordnen?
Wie viele Möglichkeiten gibt es, k Elemente aus einer Menge von n Elementen auszuwählen?

Dabei wird zwischen Permutationen (Anordnungen), Variationen und Kombinationen unterschieden. Mehr dazu siehe unten.

In den Methoden der empirischen Sozialforschung bilden die Überlegungen der Kombinatorik die wahrscheinlichkeitstheoretische Grundlage der Stichprobenziehung. Stichproben sind Teilmengen einer Grundgesamtheit und können daher als Zufallsexperiment aufgefasst werden – vorausgesetzt, es handelt sich um Zufallsstichproben.
Um Stichprobenergebnisse auf die Grundgesamtheit generalisieren zu können, ist es nötig, Realisierungswahrscheinlichkeiten für unterschiedliche Stichprobenzusammensetzungen zu ermitteln. Die verschiedenen Ziehungsverfahren bestimmen die Anzahl aller möglichen Stichproben vom Umfang k aus einer Grundgesamtheit vom Umfang n. Dazu gehört (1) ob die Reihenfolge bei der Ziehung berücksichtigt wird, ob also die Elemente einzeln gezogen und notiert oder mit einem Griff gezogen werden (sog. geordnete bzw. ungeordnete Stichproben); und (2) ob die Elemente, nachdem sie gezogen wurden, wieder »zurückgelegt« werden, d.h. bei der nächsten Ziehung der Grundgesamtheit wieder angehören, oder nicht.

Das Ziehen einer Stichprobe aus einer Grundgesamtheit soll im Folgenden mit dem Ziehen von Kugeln aus einer Urne verglichen werden.

Permutationen

Der Begriff P. (vom lat.: permutare = wechseln, vertauschen) bezeichnet alle möglichen Anordnungen einer bestimmten Zahl von Elementen und bezieht sich damit auf die erste der beiden Grundfragen der Kombinatorik. P. sind geordnete Stichproben ohen Zurücklegen. Folgendes Beispiel soll der Veranschaulichung dienen:
Die Grundgesamtheit bildet eine Urne mit vier Kugeln. Wie viele Möglichkeiten gibt es nun, die Elemente der Grundgesamtheit, also die Kugeln, anzuordnen?

Im ersten Auswahlschritt stehen vier Kugeln zur Verfügung, im zweiten nur noch drei, im dritten nur noch zwei usw. bis alle n Elemente ausgewählt sind.
Es ergeben sich 4 * 3 * 2 * 1 = 4! = 24 Möglichkeiten, die sich nur in der Reihenfolge der Elemente unterscheiden. (Das Ausrufezeichen steht für »Fakultät«, lies: vier Fakultät.)

Allgemein: Anzahl der Permutationen bzw. möglichen Anordnungen von n verschiedenen Elementen:

Variationen

V. sind Auswahlen von k Elementen aus einer Grundgesamtheit mit n Elementen mit Beachtung der Reihenfolge (also geordnete Stichproben). Das heißt bspw. dass die Kugelanordnungen (1,2) und (2,1) zwei verschiedene Auswahlen darstellen. Dabei wird noch unterschieden zwischen V. mit Zurücklegen und V. ohne Zurücklegen.

1. Variation mit Zurücklegen

Wie viele Möglichkeiten der Auswahl von k Elementen aus n Elementen gibt es, wenn nach jeder Ziehung aus der Grundgesamtheit das gerade gezogene Element wieder zurückgelegt wird?
Im Urnenbeispiel: Aus einer Urne, in der sich vier Kugeln befinden, sollen unter Berücksichtigung der Reihenfolge zwei Kugeln gezogen werden. Da jede gezogene Kugel anschließend wieder in die Urne zurückgelegt wird, kann man sowohl bei der ersten als auch bei der zweiten Ziehung aus vier Kugeln wählen.
Es ergeben sich 4 * 4 = 4² = 16 Möglichkeiten.

Allgemein: Auswahl von k Elementen aus einer Menge von n Elementen mit Zurücklegen und mit Beachtung der Reihenfolge:

Aber: In (sozialwissenschaftlichen) Stichproben gibt es normalerweise kein Zurücklegen, deshalb gilt für diesen Anwendungsfall die Variante ohne Zurücklegen.

2. Variation ohne Zurücklegen

Wie viele Möglichkeiten der Auswahl von k aus n Elementen gibt es unter Beachtung der Reihenfolge der Elemente?
Im Urnenbeispiel: Aus einer Urne mit vier Kugeln sollen unter Beachtung der Reihenfolge zwei Kugeln gezogen werden. Bei Ziehung der ersten Kugel gibt es vier, bei Ziehung der zweiten nur noch drei Kugeln zur Auswahl.
Es ergeben sich 4 * 3 = 12 Möglichkeiten.

Allgemein: Auswahl von k Elementen aus einer Menge mit n Elementen ohne Zurücklegen und mit Berücksichtigung der Reihenfolge:

Kombinationen

K sind Auswahlen von k Elementen aus einer Grundgesamtheit mit n Elementen ohne Beachtung der Reihenfolge (also ungeordnete Stichproben). Das heißt, bei den K. werden die Anordnungen der Elemente außer acht gelassen, die Kugelanordnungen (1,2) und (2,1) wären gleichwertig.
Dies entspricht der (sozialwissenschaftlichen) Stichprobenziehung, in der es gleichgültig ist, ob eine befragte Person als erste oder zweite oder dritte usw. Person gezogen wird.
Wiederum wird unterschieden zwischen K. mit Zurücklegen und K. ohne Zurücklegen.

1. Kombinationen mit Zurücklegen

Wie viele Möglichkeiten gibt es bei der Auswahl von k aus n Elementen, wenn nach jeder Ziehung das gerade gezogene Element wieder zurückgelegt wird?
Im Urnenbeispiel: Aus einer Urne mit vier Kugeln sollen zwei Kugeln gezogen werden. Da jede gezogene Kugel anschließend wieder zurückgelegt wird, kann man sowohl bei der ersten als auch bei der zweiten Ziehung aus vier Kugeln wählen.
Es ergeben sich zunächst 4 * 4 = 16 Möglichkeiten. Es müssen jedoch die Stichprobenpaare mit paarweise identischen Elementen zu einer Stichprobe zusammengefasst werden: (1,2) und (2,1) zu (1,2); (1,3) und (3,1) zu (1,3) usw. Die ursprünglich zwölf Stichproben reduzieren sich so auf sechs, insgesamt ergeben sich 10 Möglichkeiten.

Allgemein: Auswahl von k Elementen aus einer Menge von n Elementen mit Zurücklegen und ohne Berücksichtigung der Reihenfolge:

2. Kombinationen ohne Zurücklegen

Wie viele Möglichkeiten gibt es bei der Auswahl von k aus n Elementen, wenn die Reihenfolge der Elemente außer acht gelassen wird?
Im Urnenbeispiel: Aus vier Kugeln sollen zwei gezogen werden. Da es diesmal kein Zurücklegen gibt, ergeben sich zunächst 4 * 3 = 12 Möglichkeiten. Wenn nun aber zwischen den Kugelkombinationen (1,2) und (2,1), (1,3) und (3,1) etc. nicht mehr unterschieden wird (mit anderen Worten: jede Umordnung bzw. Permutation der Elemente liefert dieselbe Stichprobe), bleiben nur noch 12 / 2 = 6 Möglichkeiten.

Allgemein: Auswahl von k Elementen aus einer Menge mit n Elementen ohne Zurücklegen und ohne Berücksichtigung der Reihenfolge:

Dieser Ausdruck wird auch als Binomialkoeffizient bezeichnet, lies »n über k«. (Siehe auch den Artikel zur Binomialverteilung.)

Das bekannteste Beispiel für dieses Problem ist die Ziehung der Lottozahlen. Der Koeffizient lautet hier 49 über 6 oder gebräuchlicher »sechs aus 49« und ergibt 13.983.816 Möglichkeiten.