Mathematik-Online-Kurs: Mathematische Grundlagen-Kombinatorik-Identitäten für Binomialkoeffizienten

	[Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
	Mathematik-Online-Kurs: Mathematische Grundlagen - Kombinatorik
	Identitäten für Binomialkoeffizienten

Für Binomialkoeffizienten gelten folgende Identitäten:

$\displaystyle 2^n$	$\displaystyle =$	$\displaystyle \sum_{k=0}^n \binom{n}{k} \,,$
0	$\displaystyle =$	$\displaystyle \sum_{k=0}^n \binom{n}{k} (-1)^k\,,\quad n \geq 1\,,$
$\displaystyle \binom{n}{k}$	$\displaystyle =$	$\displaystyle \sum\limits_{i=0}^k \binom{n-k-1+i}{i}\,,\quad k < n\,,$
$\displaystyle \binom{n}{k}$	$\displaystyle =$	$\displaystyle \sum\limits_{i=0}^{n-k} \binom{k-1+i}{i}\,,\quad k > 0 \,.$

Die ersten beiden Identitäten folgen unmittelbar aus dem Binomischen Lehrsatz,

$\displaystyle (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^{n-k}b^k \,,$

mit der Wahl

bzw.

Die dritte Identität folgt durch wiederholte Anwendung der Rekursionsformel:

$\displaystyle \binom{n}{k}$	$\displaystyle =$	$\displaystyle \binom{n-1}{k} + \binom{n-1}{k-1}$
	$\displaystyle =$	$\displaystyle \binom{n-1}{k} + \binom{n-2}{k-1} + \binom{n-2}{k-2}$
	$\displaystyle =$	$\displaystyle \ldots$
	$\displaystyle =$	$\displaystyle \binom{n-1}{k} + \binom{n-2}{k-1} + \ldots + \binom{n-k-1}{0}$
	$\displaystyle =$	$\displaystyle \sum\limits_{i=0}^k \binom{n-k-1+i}{i} \,.$

Durch die Substitution $(n-k) \leftrightarrow k$ in dieser Gleichung ergibt sich die vierte Identität.

Die beiden letzten Identitäten können als Summationswege im Pascalschen Dreieck dargestellt werden.

$\includegraphics[width=0.7\linewidth]{pic_pascal}$

(Autoren: Höllig/Hörner)

automatisch erstellt am 5.5.2011