Akademik

Kombinatorik,

 

ein Zweig der Mathematik, der sich u. a. damit befasst, auf wie viele verschiedene Arten gewisse Mengen von Elementen angeordnet und zu Gruppen zusammengefasst (kombiniert) werden können. Dabei unterscheidet man einerseits, ob ein Element nur einmal oder mehrmals ausgewählt werden darf (Auswahl ohne bzw. mit Wiederholung), andererseits, ob es auf die Reihenfolge der Elemente in der Auswahl Bedeutung hat (geordnete bzw. ungeordnete Auswahl). Zwei wichtige Grundtypen von Auswahlen in der Kombinatorik sind Permutationen und Kombinationen. Erstere sind Auswahlen, die aus verschiedenen Anordnungen aller Elemente bestehen, Letztere sind mögliche Teilmengen mit einer bestimmten Anzahl von Elementen, jedoch ohne Berücksichtigung der Reihenfolge.

 

Die Kombinatorik berührt viele Gebiete der Mathematik, z. B. die Mengenlehre, die Gruppentheorie, aber auch in starkem Maße die Statistik und die Wahrscheinlichkeitsrechnung.

Kombinatorik

 

die, -, Zweig der Mathematik, in dem Fragestellungen über endliche Mengen untersucht werden, u. a., auf wie viele verschiedene Arten gewisse Mengen von Elementen angeordnet und zu Gruppen (Anordnungen) zusammengefasst (kombiniert) werden können. Jede Zusammenstellung von k ≦ n aus n vorliegenden Objekten a₁, a₂,. .., a_n, den Elementen einer gegebenen Menge A = {a₁,. .., a_n}, nennt man eine Auswahl. Es muss unterschieden werden, ob ein Element nur einmal oder mehrmals ausgewählt werden darf (Auswahl ohne beziehungsweise mit Wiederholung) und ob es auf die Reihenfolge der Elemente ankommt oder nicht (geordnete beziehungsweise ungeordnete Auswahl). In der elementaren Kombinatorik gibt es folgende Grundtypen der Auswahl:

 

1) Permutationen sind geordnete Auswahlen mit n = k; sie bestehen also aus den verschiedenen Anordnungen aller Elemente einer Menge A. Für ihre Anzahl P (n) ergibt sich: P (n) = n! (Fakultät). Beispiel: Zu drei Elementen a, b, c gibt es P (3) = 3!, also sechs verschiedene Permutationen, nämlich die Tripel: (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a). Sie können aufgefasst werden als die bijektiven Abbildungen einer Menge mit n Elementen auf sich.

 

2) Kombinationen von n Elementen zur k -ten Klasse sind die möglichen Teilmengen von A mit k Elementen ohne Berücksichtigung der Reihenfolge. Bei Kombinationen ohne Wiederholungen gibt es

 

 

solcher Kombinationen (Binomialkoeffizienten). Beispiel: Sei A = {a, b, c} und k = 2, dann gibt es

 

 

Möglichkeiten: (a, b), (a, c), (b, c).

 

Die Anzahl der Kombinationen mit Wiederholung von n Elementen zur k -ten Klasse ist

 

 

Beispiel: Bei A = {a, b, c} und k = 2 gibt es

 

 

solcher Kombinationen: (a, a), (b, b), (c, c), (a, b), (a, c), (b, c).

 

3) Variationen von n Elementen zur k-ten Klasse sind geordnete k-Tupel, also mit Berücksichtigung der Reihenfolge. Bei Variationen mit Wiederholungen ist die Anzahl n^k.

 

Beispiel: Bei A = {a, b, c} gibt es 3² = 9 solcher Variationen zur zweiten Klasse: (a, a), (b, b), (c, c), (a, b), (b, a), (a, c), (c, a), (b, c), (c, b).

 

Bei Variationen ohne Wiederholungen gibt es

 

 

Möglichkeiten. Beispiel: Bei A = {a, b, c} und k = 2 gibt es die Möglichkeiten (a, b), (b, a), (a, c), (c, a), (b, c), (c, b), also insgesamt

 

 

solcher Variationen.

 

Kombinatorische Probleme tauchen in vielen Gebieten der Mathematik auf, v. a. in der Zahlentheorie und Wahrscheinlichkeitsrechnung.