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

\underline{(7.5) SATZ:} Jede nichtleere endliche Menge T natürlicher Zahlen besitzt ein kleinstes Element und ein größtes Element.

\underline{Bew:} Vollständige Induktion nach |T | =: n ∈ IN Wir zeigen die Existenz eines kleinsten Elementes. Der andere Fall wird analog bewiesen. (IA) \underline{n = 1 :} T = \{x_{1}\}. Dann ist x_{1} ist kleinstes Element von T . (IV) Sei n ∈ IN beliebig und die Behauptung richtig für n: (IB) Jede (n + 1)-elementige Teilmenge T von IN besitzt ein kleinstes Element. Sei T = {x_{1}, x_{2}, …, x_{n}, x_{n+1}}. Die Teilmenge T′ := {x_{1}, …, x_{n}} hat dann n Elemente und besitzt nach (IV) ein kleinstes Element x_{j} ∈ T′, d.h.: x_{j} ≤ x_{i} für alle i = 1, …, n. \underline{1. Fall}: x_{j} ≤ x_{n+1} . Dann ist x_{j} kleinstes Element von T. \underline{2. Fall}: x_{n+1} ≤ x_{j} ⟹ x_{n+1} ≤ x_{i} ∀ i = 1, ⋯, n ⟹ x_{n+1} ist kleinstes Element von T. □

Wir können jetzt eine Formel beweisen, die wir früher einmal vermutet haben:

\underline{(7.6) SATZ:} Für jede endliche Menge M gilt | P(M) | = 2^{| M |} .

Bew: Induktion nach n := | M | ∈ IN_{0} : (IA) \underline{n = 0} : |M | = 0 ⟹ M = ∅ ⟹ P(M) = \{∅\}, also | P(M) | = 1 = 2^{0} (IV) Sei n ∈ IN_{0} beliebig und die Behauptung richtig für alle endlichen Mengen mit n Elementen. Sei M eine Menge mit n + 1 Elementen. Zz: | P(M) | = 2^{n+1} Sei x_{0} ∈ M fest. Setze N := M \ {x_{0}}. Dann gilt | N | = n und | P(N) | = 2^{n} nach (IV). Für eine beliebige Teilmenge U ⊆ M gilt entweder 1) x_{0} ∉ U oder 2) x_{0} ∈ U

1) x_{0} ∉ U ⟹ U ⊆ N, d.h. U ∈ P(N). Nach (IV) gibt es 2^{n} Möglichkeiten für U.

2) U = (U \ {x_{0}}) ∪^{.} {x_{0}} = V ∪^{.} {x_{0}} mit V ∈ P(N). Nach (IV) gibt es 2^{n} Möglichkeiten für V und damit auch für U .

Insgesamt: | P(M) | = 2^{n} + 2^{n} = 2 · 2^{n} = 2^{n+1} □

Ist M = {1, 2, 3, 4}, so gibt es insgesamt 2^{4} = 16 Teilmengen von M. Diese Teilmengen können 0, 1, 2, 3 oder 4 Elemente haben.

Sei P_{k}(M) = {U|U ⊆ M, | U | = k} für eine endliche Menge M.

k = 0 : ∅  1
k = 1 : {1}, {2}, {3}, {4}  4
k = 2 : {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} 6
k = 3 : {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}  4
k = 4 : M  1
\overline{16}

Um diese Zahlen formelmäßig bestimmen zu können, führen wir die Binomialkoeffizienten ein:

Chr.Nelius:Mathematik für Informatiker I (WS 2000/01) 8.12.2000 \underline{(7.7) DEF:} Für n, k ∈ IN_{0} heißt die Zahl

\binom{n}{k} := \frac{n!}{k!(n − k)!} = \frac{n · (n − 1) · . . . · (n − k + 1)}{1 · 2 · 3 · . . . · k}

Binomialkoeffizient n über k. Für 0 ≤ k ≤ n ist

\binom{n}{k} = \frac{n!}{k!(n − k)!} = \frac{n(n − 1) · . . . · (n − k + 1) \overbrace{(n − k) · . . . · 2 · 1}^{(n−k)!}}{k!(n − k)!} = \frac{n(n − 1) · . . . · (n − k + 1)}{1 · 2 · 3 · . . . · k}

Der rechtsstehende Ausdruck ist auch für k > n definiert und ergibt 0, da im Zähler 0 als Faktor auftritt.

\binom{10}{4} = \frac{10· 9̸^{3} · 8̸ · 7}{1· 2̸· 3̸· 4̸} = 210

\underline{(7.8) BEM:} a) Für 0 ≤ k ≤ n gilt \binom{n}{k} = \frac{n!}{k!(n − k)!} ∈ IN.

\binom{n}{k} = 0 für k > n, insgesamt \binom{n}{k} ∈ IN_{0}

b) \binom{n}{0} = 1 und \binom{n}{1} = n für n ≥ 1.

c) \binom{n}{k} = \binom{n}{n − k} für 0 ≤ k ≤ n

\underline{Bew:} \binom{n}{n − k} = \frac{n!}{(n − k)!(n − (n − k))!} = \frac{n!}{(n − k)!k!} = \binom{n}{k} □

d) \binom{n}{k} + \binom{n}{k − 1} = \binom{n + 1}{k} n ∈ IN_{0}, k ∈ IN

\underline{Bew:} \binom{n}{k} + \binom{n}{k − 1} = \frac{n!}{k!(n − k)!} + \frac{n!}{(k − 1)!(n − k + 1)!} = \frac{n!(n − k + 1 + k)}{k!(n − k + 1)!} =

\frac{(n + 1)!}{k!(n + 1 − k)!} = \binom{n + 1}{k} □

e) Die in d) angegebene rekursive Formel ist Grundlage für das sogenannte Pascal’sche Dreieck, mit dessen Hilfe man Binomialkoeffizienten berechnen kann.

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

\binom{0}{0}
↙  ↘
\binom{1}{0}  \binom{1}{1}
↙  ↘  ↙  ↘
\binom{2}{0}  \binom{2}{1}  \binom{2}{2}
↙  ↘  ↙  ↘  ↙  ↘
\binom{3}{0}  \binom{3}{1}  \binom{3}{2}  \binom{3}{3}
↙  ↘  ↙  ↘  ↙  ↘  ↙  ↘
\binom{4}{0}  \binom{4}{1}  \binom{4}{2}  \binom{4}{3}  \binom{4}{4}

1

↙  ↘
1  1
↙  ↘  ↙  ↘
1  2  1
↙  ↘  ↙  ↘  ↙  ↘
1  3  3  1
↙  ↘  ↙  ↘  ↙  ↘  ↙  ↘
1  4  6  4  1

\underline{(7.9) SATZ:} Sei M eine endliche Menge mit n Elementen (n ∈ IN_{0}). Dann gibt es genau \binom{n}{k} k–elementige Teilmengen von M .

\underline{Bew:} Wir zeigen durch Induktion nach n := | M | ∈ IN_{0} , daß gilt: | P_{k}(M) | = \binom{n}{k} ∈ IN .

(IA) \underline{n = 0} ⟹ M = ∅ ⟹ | P(M) | = | P_{0}(M) | = 1 und \binom{0}{0} = \frac{0!}{0!(0 − 0)!} = 1 ∈ IN

(IV) Sei n ∈ IN_{0} beliebig und die Behauptung richtig für alle endlichen Mengen mit n Elementen.

Sei | M | = n + 1. Zz: | P_{k}(M) | =^{!} \binom{n + 1}{k} = \frac{(n + 1)!}{k!(n + 1 − k)!} für 0 ≤ k ≤ n + 1

\underline{k = 0} : | P_{k}(M) | = 1 und \frac{(n + 1)!}{0!(n + 1 − 0)!} = 1

\underline{k = n + 1} : | P_{k}(M) | = 1 und \frac{(n + 1)!}{(n + 1)!(n + 1 − (n + 1))!} = 1

Sei \underline{1 ≤ k ≤ n}. M = \{x_{1}, x_{2}, …, x_{n−1}\}, N := M \ \{x_{n+1}\}, | N | = n. Für ein beliebiges U ∈ P_{k}(M) gilt dann genau einer der beiden folgenden Fälle: 1.Fall: x_{n+1} ∉ U ⟹ U ⊆ N. Nach (IV) gibt es \binom{n}{k} Möglichkeiten für U.

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

2.Fall: x_{n+1} ∈ U ⟹ U =\overbrace{(U \ \{x_{n+1}\}}^{=V}) ∪^{.} \{x_{n+1}\} mit V ∈ P_{k−1}(N) .

Für V (und damit U) gibt es nach (IV) \binom{n}{k − 1} Möglichkeiten. Insgesamt also aus beiden Fällen \binom{n}{k} + \binom{n}{k − 1} = \binom{n + 1}{k} Möglichkeiten für U. □

\underline{(7.10) BEM:} ∑_{k=0}^{n} \binom{n}{k} = ∑_{k=0}^{n} | P_{k}(M) | = | P(M) | = 2^{n}

\underline{Beispiele:} 1. Wieviele Tipreihen gibt es beim Lotto 6 aus 49?

\binom{49}{6} = \frac{49 · 48 · 47 · 46 · 45 · 44}{1 · 2 · 3 · 4 · 5 · 6} = 13.983.816

2. Wieviele Möglichkeiten für ”3 Richtige” gibt es bei einer Ausspielung?

\binom{6}{3} · \binom{49 − 6}{3} = \binom{6}{3} · \binom{43}{3} = 246.820

Wahrscheinlichkeit für “3 Richtige“: W = \frac{Anzahl der günstigen Fälle}{Anzahl der möglichen Fälle} = \frac{246.820}{13.983.816} = 0, 01765... d.h. ca 1,8% aller möglichen Tipreihen bringen bei einer Ausspielung 3 Richtige.

3. Wieviele Möglichkeiten gibt es, beim Skatspiel (32 Karten) ein Blatt aus 10 Karten zu bekommen? \binom{32}{10} = 64.512.240 (Mehr Möglichkeiten als in 1.!)

4. Wieviele Möglichkeiten gibt es beim Skatspiel, genau 3 Buben und 2 Asse zu bekommen? \binom{4}{3} · \binom{4}{2} · \binom{24}{5} = 1.020.096 Die Wahrscheinlichkeit ist 0,01581...

Woher kommt der Name Binomialkoeffizient?

(a + b)^{0} = 1  1
(a + b)^{1} = a^{1} + b^{1}  1  1
(a + b)^{2} = a^{2} + 2ab + b^{2}  1  2  1
(a + b)^{3} = a^{3} + 3a^{2}b + 3ab^{2} + b^{3}  1  3  3  1
(a + b)^{4} = a^{4} + 4a^{3}b + 6a^{2}b^{2} + 4ab^{3} + b^{4}  1  4  6  4  1

\underline{(7.11) SATZ:} (Binomialsatz) Für alle x, y ∈ IR und n ∈ IN gilt

(x + y)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{n−k}y^{k}