combinatorial interpretation of the binomial coefficient

1. Satz

2. Beweis

2.1. durch vollständige Induktion

2.1.1. Induktionsanfang

2.1.1.1. Leere Menge
\begin{align*} \binom{0}{0} = \prod_{j=1}^{0} \frac{0 - j + 1}{j} = \frac{0!}{0!\cdot 0!} = 1 \end{align*}
  1. Einelementige Menge
    • Teilmenge von \(\{A_1\}\):
      • Leere Menge \(\emptyset \Rightarrow 1 = \binom{1}{0}\) (siehe: leere Produkt)
      • Einelementig: $\{A1\} ⇒ 1 = \binom{1}{1} = ∏j=11 \frac{1 - 1 + 1}{j} = 1 $
2.1.1.2. k

Triviale Fälle

\begin{align*} \binom{n}{0} =& 1 \\ \binom{n}{n + i} =& 0 \quad i \in \mathbb{N}^+ \end{align*}

2.1.2. Induktionsschritt

über Binomialkoeffizient - Hilfssatz Annahme:

  • Erhöhen der Menge (Mächtigkeit: \(\vert n \vert\)) um das Element \(A_{n+1}\)
    • neue Möglichkeiten:
      • Mengen ohne \(A_{n+1} \Rightarrow \binom{n}{k}\)
      • Mengen mit \(A_{n+1} \Rightarrow \binom{n}{k-1}\) (weil Platz gemacht werden muss)
\begin{align*} \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k} \end{align*}

2.2. Alternativ

TODO aus Königsberger

Date: nil

Author: Anton Zakrewski

Created: 2024-10-11 Fr 21:25