Chr.Nelius:Mathematik für Informatiker I (WS 2000/01) 15.12.2000

§8. Elementare Kombinatorik

Wir wollen hier einfache Abzählverfahren für die Elemente einer endlichen Menge behandeln, die durch bestimmte Eigenschaften definiert sind.

Wir unterscheiden Permutationen und Kombinationen.

Permutation: geordnete Auswahl von k Elementen aus einer n–elementigen Menge

(1) ohne Wiederholung

(2) mit Wiederholung

Kombination: ungeordnete Auswahl von k Elementen aus einer n–elementigen Menge

(3) ohne Wiederholung

(4) mit Wiederholung

Beispiele: (1) Wieviele Möglichkeiten gibt es, n verschiedene Bücher in ein Fach eines Bücherregals zu stellen ?

(2) Wieviele Möglichkeiten gibt es, aus 4 Buchstaben Wörter der Länge 3 mit paarweise verschiedenen Buchstaben zu bilden ?

(3) Wie groß ist die Anzahl der Lotto–Tipreihen beim Spiel 6 aus 49 ?

(4) Wieviele Farbverteilungen gibt es, wenn aus einer Kiste mit je 10 blauen, grünen,roten, schwarzen und weißen Kugeln 6 Kugeln herausgenommen werden ?

Permutationen

\underline{(8.1) DEF:} Sei M eine endliche Menge mit n Elementen. Eine Permutation von (Elementen aus) M ist ein n–Tupel (x_{1}, x_{2}, …, x_{n}) ∈ M^{n}, das aus paarweise verschiedenen Elementen aus M besteht.

Eine Permutation von M ist also eine Umordnung der Elemente von M.

\underline{(8.2) SATZ:} Ist M eine endliche Menge mit n Elementen, so gibt es n! Permutationen von M.

\underline{(8.3) Beispiel:} Wie viele verschiedene Wörter lassen sich aus den Buchstaben A, A, A, B, B, C, C bilden?

\underline{(8.4) SATZ:} Die Anzahl der Permutationen einer Multimenge M = {{x_{1}, …, x_{1}, x_{2}, …, x_{2}, …, x_{r}, …, x_{r}}}, in der das Element x_{i} genau k_{i}–mal vorkommt (i = 1, 2, …, r) ist gleich dem Multinomialkoeffizienten

\binom{n}{k_{1}, k_{2}, …, k_{r}} := \frac{n!}{k_{1}!k_{2}! ⋯ k_{r}!}

wobei n = k_{1} + k_{2} + … + k_{r} ist.

Chr.Nelius:Mathematik für Informatiker I (WS 2000/01) 15.12.2000

\underline{(8.5) DEF:} Sei M eine endliche Menge mit n Elementen und k ∈ IN eine natürliche Zahl mit 1 ≤ k ≤ n. Eine k–Permutation von (Elementen aus) M ist ein k–Tupel (x_{1}, x_{2}, …, x_{k}) ∈ M^{k}, das aus paarweise verschiedenen Elementen aus M besteht.

Eine n–Permutation ist gerade eine Permutation von M .

\underline{(8.6) SATZ:} Die Anzahl P (n, k) (1 ≤ k ≤ n) aller k–Permutationen einer n–elementigen Menge ist

P (n, k) = n · (n − 1) · . . . · (n − k + 1)

Die Anzahl aller Permutationen einer Menge mit n Elementen ist gleich n!. (s. (8.2)).

\underline{(8.7) DEF:} Ein k–Tupel aus M^{k} heißt auch eine k–Permutation mit Wiederholung von (Elementen aus) M

\underline{(8.8) SATZ:} Sei k ∈ IN beleibig. Die Anzahl P_{w}(n, k) der k–Permutationen mit Wiederholung einer n–elementigen Menge ist gleich n^{k}.

\underline{(8.9) BEM:} Sei M eine endliche Menge mit n Elementen. Jedes k–Tupel (x_{1}, x_{2}, …, x_{k}) ∈ M^{k} definiert dann eine Abbildung

f : {1, 2, 3, …, k} ⟶ M , f(i) := x_{i} (∀ i ∈ {1, 2, 3, …, k}

a) Die Anzahl aller Abbildungen einer k–elementigen Menge in eine n–elementigen Menge ist daher n^{k}.

b) Ist (x_{1}, x_{2}, …, x_{k}) eine k–Permutation, so muß k ≤ n gelten, und die zugehörige Abbildung ist injektiv. Daher ist P (n, k) auch die Anzahl aller injektiven Abbildungen einer k–elementigen Menge in eine n–elementige Menge.

c) Im Falle k = n ist eine injektive Abbildung f : {1, 2, 3, …, k} ⟶ M = {x_{1}, x_{2}, …, x_{n}} auch bijektiv (s. Aufgabe 32d)), d.h. P (n, n) = n! ist die Anzahl aller bijektiven Abbildungen einer n–elementigen Menge in eine n–elementige Menge.

Kombinationen

Bei einer Permutation ist die Reihenfolge der ausgewählten Objekte relevant, bei einer Kombination nicht mehr.

\underline{(8.10) DEF:} Sei M eine endliche Menge mit n Elementen und k ∈ IN eine natürliche Zahl mit 1 ≤ k ≤ n. Eine k–Kombination von (Elementen aus) M ist eine k–elementige Teilmenge von M.

\underline{(8.11) SATZ:} Für die Anzahl C(n, k) der k–Kombinationen von n Elementen gilt

C(n, k) = \binom{n}{k}