Die Pascal-Regel

Pascal-Regel und Teilmengenstrukturen · Abschnitt 21 von 64

Gelöstes Beispiel

Ein Element als Weiche

Die Pascal-Regel und Teilmengen als Binärwörter machen Binomialkoeffizienten lebendig. Jede $k$ -Auswahl enthält ein festes Element $a$ oder nicht. Im ersten Fall fehlen $k-1$ aus $n-1$ , im zweiten $k$ aus $n-1$ .

Satz

Pascal-Regel

$\binom nk=\binom{n-1}{k-1}+\binom{n-1}k$ . Die beiden Summanden zählen disjunkte und vollständige Fälle.

Intuition

Pascal-Dreieck

Randwerte sind 1. Jeder innere Eintrag ist die Summe der beiden darüberliegenden, weil genau die Pascal-Regel wiederholt angewendet wird.