Kombination (Kombinatorik)

Grundidee und Abgrenzung

Eine Kombination oder ungeordnete Stichprobe ist eine Auswahl von k Objekten aus einer Grundmenge mit n Objekten, bei der die Reihenfolge keine Rolle spielt. Anders als bei einer Permutation müssen nicht alle Objekte der Grundmenge ausgewählt werden. Die Bestimmung der möglichen Kombinationen gehört zu den Standardaufgaben der abzählenden Kombinatorik.

Man unterscheidet zwei Fälle:

• Bei einer Kombination ohne Wiederholung darf jedes Objekt höchstens einmal vorkommen. Im Urnenmodell entspricht dies dem Ziehen ohne Zurücklegen.
• Bei einer Kombination mit Wiederholung darf dasselbe Objekt mehrfach ausgewählt werden. Im Urnenmodell entspricht dies dem Ziehen mit Zurücklegen.

Spielt bei einer Auswahl die Reihenfolge eine Rolle, obwohl nicht alle Objekte vorkommen müssen, heißt sie Variation. Müssen alle Objekte vorkommen und wird ihre Reihenfolge berücksichtigt, handelt es sich um eine Permutation.

Kombinationen ohne Wiederholung

Werden k verschiedene Objekte aus n Objekten ausgewählt und bleibt ihre Reihenfolge unberücksichtigt, beträgt die Anzahl

n! / ((n−k)! · k!) = (n über k).

Der Ausdruck (n über k) heißt Binomialkoeffizient. Die Formel lässt sich aus den n!/(n−k)! geordneten Auswahlen herleiten: Jede ungeordnete Auswahl erscheint darin in k! verschiedenen Reihenfolgen, weshalb durch k! geteilt wird. Außerdem gilt (n über k) = (n über n−k). Es ist für die Anzahl also unerheblich, ob man die k ausgewählten oder die n−k nicht ausgewählten Objekte betrachtet.

Eine Kombination lässt sich durch einen Vektor (x₁, x₂, …, xₙ) mit xᵢ ∈ {0,1} und x₁ + … + xₙ = k darstellen. Dabei zeigt eine 1 an, dass das jeweilige Objekt ausgewählt wurde. Alternativ kann man die Nummern der ausgewählten Objekte als streng wachsende Folge schreiben: 1 ≤ z₁ < z₂ < … < zₖ ≤ n.

Eine weitere Deutung teilt die Grundmenge in zwei Klassen ein: ausgewählt und nicht ausgewählt. Betrachtet man nur diese Klassenzugehörigkeit, ergibt die Anzahl der unterscheidbaren Anordnungen wieder den Binomialkoeffizienten. Dieser Ansatz wird unter anderem bei Bernoulli-Experimenten verwendet.

Beispiele ohne Wiederholung

Beim Lotto „6 aus 49“ werden sechs verschiedene Kugeln gezogen; ihre Reihenfolge ist für die Gewinnzahlen unwichtig. Daher gibt es

(49 über 6) = 49!/(6! · 43!) = 13.983.816

mögliche Auswahlen. Das Produkt 49 · 48 · 47 · 46 · 45 · 44 zählt zunächst alle Ziehungsreihenfolgen. Da jede Auswahl in 6! Reihenfolgen vorkommt, wird durch 6! geteilt.

Sollen die sechs aufsteigend geordneten Lottozahlen z₁, …, z₆ jeweils mindestens die Differenz 5 haben, ordnet man ihnen z₁, z₂−4, z₃−8, z₄−12, z₅−16, z₆−20 zu. Dadurch entstehen sechs verschiedene Zahlen zwischen 1 und 29. Die Zuordnung ist umkehrbar und damit bijektiv, also eindeutig in beide Richtungen. Deshalb beträgt die gesuchte Anzahl

(29 über 6) = 29!/(6! · 23!) = 475.020.

Bei der Aufteilung von 22 Fußballspielern in zwei unterscheidbare Teams mit je 11 Spielern genügt es, das erste Team auszuwählen. Es gibt (22 über 11) = 705.432 Möglichkeiten. Sind die beiden Teams nicht nummeriert, wird jede Aufteilung doppelt gezählt; dann bleiben ½ · (22 über 11) = 352.716 Möglichkeiten. Für die Auswahl von zwei Schiedsrichtern aus 16 Personen gibt es entsprechend (16 über 2) = 120 Möglichkeiten.

Auch kürzeste Gitterwege werden so gezählt. Sind insgesamt neun Schritte nötig, davon fünf nach rechts und vier nach unten, kann man die Positionen der fünf Rechtsschritte wählen: (9 über 5) = 126 Wege. Beim Deo-Gracias-Fresko führen vier entsprechende Richtungsvarianten zu insgesamt 126 · 4 = 504 Möglichkeiten. Für das Lesen von MANHATTANSUNSET mit sieben Schritten nach rechts und sieben nach unten ergeben sich (14 über 7) = 3.432 Wege. Solche Aufgaben heißen Manhattan-Probleme.

Kombinationen mit Wiederholung

Bei einer Kombination mit Wiederholung werden k Elemente aus n möglichen Elementen ausgewählt. Die Reihenfolge ist unwichtig, aber ein Element darf mehrfach vorkommen. Die Anzahl lautet

(n+k−1)! / ((n−1)! · k!) = (n+k−1 über k) = (n+k−1 über n−1).

Dafür wird auch die Schreibweise des Multimengenkoeffizienten verwendet. Eine Multimenge ist eine Menge, in der Elemente mehrfach vorkommen dürfen. Für n = 5 und k = 3 erhält man

(7 über 3) = 7!/(3! · 4!) = 35.

Eine solche Kombination kann als Vektor (x₁, x₂, …, xₙ) beschrieben werden, wobei xᵢ ∈ {0,1,…,k}, x₁ + … + xₙ = k und xᵢ die Häufigkeit des i-ten Elements angibt. Alternativ schreibt man die ausgewählten Nummern als nicht abnehmende Folge: 1 ≤ z₁ ≤ z₂ ≤ … ≤ zₖ ≤ n.

Die Formel kann durch eine Bijektion zu Kombinationen ohne Wiederholung erklärt werden: Die 35 Kombinationen mit Wiederholung von drei aus fünf Objekten entsprechen genau den 35 Kombinationen ohne Wiederholung von drei aus sieben Objekten.

Beispiele mit Wiederholung

Beim Gummibärchen-Orakel werden fünf Bärchen aus einem großen Vorrat mit genau fünf Farben ausgewählt. Würde die Reihenfolge zählen, gäbe es 5⁵ = 3.125 Variationen mit Wiederholung. Ohne Berücksichtigung der Reihenfolge gibt es dagegen

(9 über 5) = 9!/(5! · 4!) = 126

Kombinationen. Darunter sind 5 Kombinationen mit nur einer Farbe, 40 mit zwei, 60 mit drei, 20 mit vier und 1 mit allen fünf Farben. Ebenfalls 126 Möglichkeiten entstehen bei der Auswahl von vier Stiften aus einem Vorrat mit sechs Farben.

Werden aus einer Urne mit fünf nummerierten Kugeln dreimal Kugeln mit Zurücklegen gezogen und wird die Reihenfolge ignoriert, gibt es (7 über 3) = 35 Kombinationen. Sie sind dreielementige Multimengen aus {1,2,3,4,5}.

Bei drei Würfeln existieren 6³ = 216 geordnete Ergebnisse. Werden die Würfel gleichzeitig betrachtet, sind etwa (1,1,2), (1,2,1) und (2,1,1) nicht unterscheidbar. Daher gibt es nur

(8 über 3) = 8!/(3! · 5!) = 56

ungeordnete Würfe. Davon zu unterscheiden ist die Augensumme: Sie kann lediglich 16 verschiedene Werte von 3 bis 18 annehmen.

Auch Summendarstellungen lassen sich als Kombinationen mit Wiederholung auffassen. Soll 4 als Summe von drei natürlichen Zahlen größer oder gleich 0 dargestellt werden, gibt jeder Summand an, wie oft eines von drei Objekten gewählt wurde. Es gibt

(6 über 4) = 6!/(4! · 2!) = 15

Darstellungen. Beim Sterne-und-Striche-Verfahren stehen vier Sterne für die zu verteilenden Einheiten und zwei senkrechte Striche für die Trennung der drei Summanden. Die 15 Darstellungen entsprechen den Möglichkeiten, vier Sterne auf sechs Positionen anzuordnen.