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

\underline{(8.12) DEF:} Es sei M eine endliche Menge mit n Elementen und k ∈ IN. Eine k–Kombination von (Elementen aus) M mit Wiederholung ist eine k–elementige Multimenge aus Elementen von M.

\underline{(8.13) SATZ:} Für die Anzahl C_{w}(n, k) der k–Kombinationen von n Elementen mit Wiederholung gilt

C_{w}(n, k) = \binom{n + k − 1}{k}

Denk–Vorstellungen

k–Permutation von n Elementen (k ≤ n):

(1) Aus einer Urne mit n verschiedenen Objekten wird k-mal ein Objekt gezogen (und nicht wieder zurückgelegt). Dabei wird die Reihenfolge der Ziehungen notiert.

(2) k verschiedene Objekte werden in n verschiedene Fächer verteilt, wobei in jedes Fach höchstens ein Objekt gelegt wird. Jede solche Verteilung kann als k–Permutation der n Fächer aufgefaßt werden.

k–Permutation mit Wiederholung von n Elementen (k ∈ IN):

(1) Die gezogenen Elemente werden wieder zurückgelegt.

(2) Die Einschränkung ”höchstens ein Element” wird fallengelassen.

Beispiele:

• Wörter einer Sprache

• Zahldarstellungen im Dezimalsystem

• Toto–Tips

k–Kombination von n Elementen (k ≤ n):

(1) Aus einer Urne mit n verschiedenen Objekten wird k-mal ein Objekt gezogen (und nicht wieder zurückgelegt). Dabei ist die Reihenfolge der Ziehungen bedeutungslos.

Beispiele:

• Tips beim Zahlenlotto

• Blattverteilungen beim Skat

• Anzahl der Binärfolgen der Länge n, in denen an genau k Stellen eine 1 steht

k–Kombination mit Wiederholung von n Elementen (k ∈ IN):

(1) Aus einer Urne mit n Objekten wird k–mal ein Objekt gezogen. Dabei wird ein gezogenes Objekt wieder zurückgelegt, und man notiert dabei, wie oft ein Objekt gezogen wurde.

(2) Es sind n Typen von Objekten gegeben (dies entspricht den Elementen von M). Eine k–Kombination mit Wiederholung gibt an, wieviel Stück von jedem Typ (insgesamt k) gewählt werden.

Das Zählen von Abbildungen

\underline{(8.14) SATZ:} M und N seien nichtleere Mengen mit | M | = k und | N | = n. Dann gilt:

a) Es gibt n^{k} Abbildungen M ⟶ N (8.9a)

b) Es gibt P (n, k) injektive Abbildungen M ⟶ N (8.9b)

c) Es gibt n! bijektive Abbildungen M ⟶ N (8.9c) mit k = n

d) Es gibt S(k, n) · n! surjektive Abbildungen M ⟶ N , wobei S(k, n) die Anzahl der n–Zerlegungen einer k–elementigen Menge ist. S(k, n) heißt Stirling–Zahl 2. Art.