Kombinationsfunktion

Der Begriff Kombinationsfunktion bezeichnet in der Mathematik Funktionen, die sich mit der Bildung oder Zählung von Kombinationen befassen. Sie kann entweder die Sammlung aller k-Element-Kombinationen eines endlichen Trägers X liefern oder deren Anzahl bestimmen. In der häufigsten Form betrifft sie eine endliche Menge S mit n Elementen und eine Wahlgröße k mit 0 ≤ k ≤ n.

Die erzeugende Version lautet K_k(S) = {A ⊆ S | |A| = k}. Die Anzahl der solcher Teilmengen ist C(n,k) = n! / (k!(n−k)!). Typische Eigenschaften sind C(n,k) = C(n,n−k) und die Rekurrenz C(n,k) = C(n−1,k) + C(n−1,k−1). Generell ergeben sich weitere Ansätze über Generating-Funktionen, etwa der Zusammenhang mit der Potenzreihe (1+x)^n.

Varianten umfassen Kombinationen ohne Wiederholung (wie beschrieben) sowie Kombinationen mit Wiederholung, bei denen die Anzahl der Kombinationen C(n+k−1,k) beträgt. In der Praxis verbinden sich algorithmische Berechnungen (z. B. mit Pascal-Dreieck oder dynamische Programmierung) und symbolische Ausdrücke.

Anwendungen finden sich in der Wahrscheinlichkeitsrechnung (Hypergeometrische Verteilung), der Statistik, der Kombinatorik in der Optimierung sowie in der Enumerationsproblematik bei der Planung von Gruppen oder Teams. Beispiele: Aus einer Menge von 6 Objekten wählt man 3 zu einer Teilkollektion, was 20 Möglichkeiten ergibt (C(6,3)=20).