Rechenregeln für Binomialkoeffizienten

Studium

\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}

Voraussetzung: $n, k \in \mathbb{N}_0;$ $\binom{n}{k} = 0$ $für$ $k > n$

$\binom{n}{k}$: Binomialkoeffizient „n über k“, Anzahl der k-elementigen Teilmengen einer n-elementigen Menge
$n$: Größe der Grundmenge
$k$: Größe der ausgewählten Teilmenge

Die Pascalsche Regel und verwandte Identitäten erlauben, Binomialkoeffizienten ohne Fakultäten zu berechnen und Summen zu vereinfachen.

Erklärung

Die Pascalsche Regel baut das Pascalsche Dreieck auf: Jeder Eintrag ist die Summe der beiden darüberliegenden. Kombinatorischer Beweis: Von den $(k+1)$ -elementigen Teilmengen von $\{1, \ldots, n+1\}$ enthalten $\binom{n}{k}$ das Element $n+1$ (die übrigen $k$ Elemente wählt man aus $n$ ), und $\binom{n}{k+1}$ enthalten es nicht.

Weitere wichtige Regeln für $n, k \in \mathbb{N}_0$ :

Name	Identität
Symmetrie	$\binom{n}{k} = \binom{n}{n-k}$ für $k \leq n$
Absorption	$k \binom{n}{k} = n \binom{n-1}{k-1}$ für $n, k \geq 1$
Zeilensumme	$\sum_{k=0}^{n} \binom{n}{k} = 2^n$
Alternierende Summe	$\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0$ für $n \geq 1$
Vandermonde	$\sum_{j=0}^{k} \binom{m}{j} \binom{n}{k-j} = \binom{m+n}{k}$
Summe der Quadrate	$\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$
Hockeyschläger	$\sum_{i=k}^{n} \binom{i}{k} = \binom{n+1}{k+1}$

Zeilensumme und alternierende Summe folgen aus dem binomischen Lehrsatz mit $(1+1)^n$ und $(1-1)^n$ . Die Summe der Quadrate ist der Spezialfall $m = n = k$ von Vandermonde, zusammen mit der Symmetrie.

Beispiele

Pascal: Aus $\binom{9}{3} = 84$ und $\binom{9}{4} = 126$ folgt $\binom{10}{4} = 84 + 126 = 210$ .

Absorption: $5 \cdot \binom{9}{5} = 9 \cdot \binom{8}{4}$ , also $5 \cdot 126 = 9 \cdot 70 = 630$ .

Vandermonde: Aus $3$ Frauen und $4$ Männern werden $3$ Personen gewählt. Nach Anzahl der Frauen aufgeteilt:

\binom{3}{0}\binom{4}{3} + \binom{3}{1}\binom{4}{2} + \binom{3}{2}\binom{4}{1} + \binom{3}{3}\binom{4}{0} = 4 + 18 + 12 + 1 = 35 = \binom{7}{3}

Hockeyschläger: $\binom{2}{2} + \binom{3}{2} + \ldots + \binom{6}{2} = 1 + 3 + 6 + 10 + 15 = 35 = \binom{7}{3}$ .

Summe der Quadrate für $n = 4$ : $1 + 16 + 36 + 16 + 1 = 70 = \binom{8}{4}$ .

Typische Fehler

Indizes in der Pascalschen Regel verschieben. $\binom{n}{k} + \binom{n}{k+1}$ ergibt $\binom{n+1}{k+1}$ , nicht $\binom{n+1}{k}$ und nicht $\binom{2n}{2k+1}$ .
Unten addieren. $\binom{n}{k} + \binom{n}{j}$ ist im Allgemeinen nicht $\binom{n}{k+j}$ : $\binom{4}{1} + \binom{4}{1} = 8$ , aber $\binom{4}{2} = 6$ . Die Pascalsche Regel addiert nur Nachbarn in derselben Zeile.
Alternierende Summe für $n = 0$ . Dort ist sie $\binom{0}{0} = 1$ , nicht $0$ .

Rechenregeln für Binomialkoeffizienten