icon-Kombinatorik Mathe Tutorial: Kombinatorik

Kombinatorik

Die Kombinatorik ist die Lehre von der Zusammen­stellung abzählbar vieler Objekte. Dabei steht im Allgemeinen die Anzahl der Möglichkeiten für eine gewisse Zusammen­stellung im Vordergrund, da sich daraus eine Aussage über die Wahrscheinlichkeit einer bestimmten Zusammen­stellung ableiten lässt. Man unterscheidet bei den Zusammen­stellungen zwischen Permutationen, Variationen und Kombinationen der Objekte.

Aufgabenstellungen der Kombinatorik

Wie viele Möglichkeiten gibt es Bücher in einem Regal anzuordnen? (Permutation)

An einem Wettrennen nehmen Teilnehmer teil. Wie viele Möglichkeiten gibt es für die Erstplazierten in der Reihenfolge des Wettkampfergebnisses? (Variation ohne Wiederholungen)

Wieviele verschiedene Wörter mit Buchstaben kann man aus einem Alphabet mit Buchstaben bilden? (Variation mit Wiederholungen)

Wieviele Möglichkeiten gibt es beim Zahlenlotto Zahlen aus Zahlen auszuwählen? (Kombination ohne Wiederholungen)

Wieviele verschiedene Würfe kann man mit gleichen Würfeln mit jeweils Seiten erzielen? (Kombination mit Wiederholungen)

Weiterführende Artikel bei Wikipedia

Kombinatorische Grundfunktionen

Zusammenstellung der Grundfunktionen für die Kombinatorik.

Fakultät

Die Funktion f(n) = n! für die gilt f(0) = 1 und f(n) = n ⋅ f(n-1) heißt n-Fakultät.

Beispiel: 5! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120

Binomialkoeffizient

Die für alle natürlichen Zahlen definierte Funktion n k heißt Binomialkoeffizient.

Der Binomialfoeffizient ist folgendermaßen definiert:

n k = n! k! n - k !

mit0kn andernfalls ist n k = 0

Rechner: Binomialkoeffizient

n= k=

Eigenschaften der Binomialkoeffizienten

Symmetriesatz: n k = n n-k

Additionssatz: n k + n k+1 = n+1 k+1

Binomischer Satz

Für alle reellen Zahlen a und b und alle natürlichen Zahlen n gilt der binomische Satz:

a + b n = k = 0 n n k a n - k b k = n 0 a n b 0 + n 1 a n - 1 b 1 + ... + n n a 0 b n

Rechner: Binomischer Satz

n=

Polynomialkoeffizienten

Die Binomialkoeffizienten sind ein Spezialfall der allgemeineren Polynomialkoeffizienten. Die Polynomialkoeffizienten sind erklärt für alle natürlichen n und alle r-Tupel natürlicher ki für die die Summe gleich n ist.

Die Polynomialkoeffizienten sind folgendermaßen definiert:

n k1,k2,...,kr = n! k1! k2! ... kr!

mit i = 1 r ki = n

Beispiel

12 2,3,3,4 = 12! 2! 3! 3! 4! = 277200

Polynomischer Satz

Für alle r-Tupel reeller Zahlen a1, a2, ..., ar und alle natürlichen Zahlen n gilt der polynomische Satz. Dabei ist die Summe über alle Kombinationen der r-Tupel zu bilden für die die Summe gleich n ist.

a1 + a2 + ... + ar n = k1 + k2 + ... + kr = n n k1,k2,...,kr a1k1 a2k2 ... arkr

Permutationen

Als Permutation Pk bezeichnet man die Aneinanderreihung von k Elementen unter Beachtung der Position der Elemente in der Reihe. Eine Fragesteluung der Kombinatorik ist wie viele Anordnungen A von k Elementen gibt es.

Es gilt:

A Pk = k!

Variationen

Als Variation Vkr ohne Wiederholung bezeichnet man die geordnete Auswahl von r Elementen aus einer Gesamtheit von k Elementen. Der Unterschied zu Kombinationen besteht in der Beachtung der Reihenfolge. Wenn z.B. an einem Turnier k Mannschaften teilnehmen ist die Anzahl der möglichen drei Erstplazierten eine Variation ohne Wiederholungen da jede Mannschaft nur einen Platz belegen kann und die Position unter den ersten drei relevant ist.

Es gilt für Variationen ohne Wiederholungen:

A Vrk = k! k - r !

Es gilt für Variationen mit Wiederholungen:

A Vrk = k r

Kombinationen

Als Kombination Ckr bezeichnet man die Auswahl von r Elementen aus einer Gesamtheit von k Elementen. Im Gegensatz zu den Variationen spielt die Reihenfolge keine Rolle. Z.B. sind die Lottozahlen eine Kombination ohne Wiederholung, da die gezogenen Zahlen nicht zurückgelegt werden.

Es gilt für Kombinationen ohne Wiederholungen:

A Crk = k r = k! r! k - r !

Es gilt für Kombinationen mit Wiederholungen:

A Crk = k+r-1 r = k+r-1! r! k - 1 !