Mathe Hochschule TU München Vorkurs Mathematik für Informatiker Aufgaben zum Thema Kombinatorik

Aufgaben zum Thema Kombinatorik

Gib die Koeffizienten des Polynoms $(1 + x)^{n}$ mittels Binomialkoeffizienten an und zeige durch geschickes Verwenden dieser Formel

$\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}$ und, falls n>0, $\sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) = 0$

Für diese Aufgabe benötigst Du folgendes Grundwissen: Kombinatorik

Zuerst geben wir die Koeffizienten von $(x + 1)^{n}$ an (Beweis ist der Vollständigkeit angehängt; laut der Aufgabenstellung reicht das bloße Angeben):

(x + 1)^{n} = \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k}

Nun versuchen wir, darüber $2^{n}$ darzustellen:

2^{n} = (1 + 1)^{n} = \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) 1^{k} = \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) ■

Ähnlich verfahren wir mit der zweiten angegebenen Gleichung (mit der Bedingung $n > 0$ ):

0 = 0^{n} = (1 - 1)^{n} = \sum_{k = 0}^{n} (- 1)^{k} (\begin{array}{c} n \\ k \end{array}) ■

Anhang

Zuerst müssen wir

(\begin{array}{c} n \\ k - 1 \end{array}) + (\begin{array}{c} n \\ k \end{array}) = (\begin{array}{c} n + 1 \\ k \end{array})

zeigen:

(\begin{array}{c} n \\ k - 1 \end{array}) + (\begin{array}{c} n \\ k \end{array}) = \frac{n!}{(k - 1)! (n - (k - 1))!} + \frac{n!}{k! (n - k)!} = \frac{n!}{(k - 1)! (n - k + 1)!} + \frac{n!}{k! (n - k)!} = \frac{n!}{(k - 1)! (n - k)!} \cdot \frac{1}{n - k + 1} + \frac{n!}{k! (n - k)!} = \frac{n!}{(k - 1)! (n - k)!} \cdot \frac{k}{k} \cdot \frac{1}{n - k + 1} + \frac{n!}{k! (n - k)!} = \frac{n!}{k (k - 1)! (n - k)!} \cdot \frac{k}{n - k + 1} + \frac{n!}{k! (n - k)!} = \frac{n!}{k! (n - k)!} \cdot \frac{k}{n - k + 1} + \frac{n!}{k! (n - k)!} = \frac{n!}{k! (n - k)!} (1 + \frac{k}{n - k + 1}) = \frac{n!}{k! (n - k)!} (\frac{n - k + 1}{n - k + 1} + \frac{k}{n - k + 1}) = \frac{n!}{k! (n - k)!} \cdot \frac{n + 1}{n - k + 1} = \frac{(n + 1)!}{k! ((n + 1) - k)!} = (\begin{array}{c} n + 1 \\ k \end{array})

Mit dieser Gleichung können wir nun einen Induktionsbeweis führen mit der Induktionsvoraussetzung:

(x + 1)^{n} = \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k}, n \in ℕ_{𝟘}

Beginnen wir bei $n = 0$ und betrachten auch $n = 1$ :

(x + 1)^{0} = 1 = (\begin{array}{c} 0 \\ 0 \end{array})

(x + 1)^{1} = x + 1 = (\begin{array}{c} 1 \\ 0 \end{array}) x + (\begin{array}{c} 1 \\ 1 \end{array})

Nun können wir den Induktionsschritt von $n \to n + 1$ durchführen:

(x + 1)^{n + 1} = (x + 1) (x + 1)^{n} \overset{I V}{=} (x + 1) \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k} = x \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k} + \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k} = \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k + 1} + \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k} = \sum_{k = 1}^{n + 1} (\begin{array}{c} n - 1 \\ k \end{array}) x^{k} + \sum_{k = 0}^{n} (\begin{array}{c} n \\ k \end{array}) x^{k} = (\begin{array}{c} n \\ n \end{array}) x^{n + 1} + (\begin{array}{c} n \\ 0 \end{array}) x^{0} + \sum_{k = 1}^{n} ((\begin{array}{c} n \\ k \end{array}) + (\begin{array}{c} n \\ k - 1 \end{array})) x^{k} = (\begin{array}{c} n + 1 \\ n + 1 \end{array}) x^{n + 1} + (\begin{array}{c} n + 1 \\ 0 \end{array}) x^{0} + \sum_{k = 1}^{n} (\begin{array}{c} n + 1 \\ k \end{array}) x^{k} = \sum_{k = 0}^{n + 1} (\begin{array}{c} n + 1 \\ k \end{array}) x^{k} ■

Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0 → Was bedeutet das? serlo.org