Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen] Englische Flagge

Mathematik-Online-Kurs: Vorkurs Mathematik - Grundlagen - Kombinatorik

Identitäten für Binomialkoeffizienten


[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]

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 $ a=b=1$ bzw. $ a=-b=1$.

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)

[vorangehende Seite] [nachfolgende Seite] [Gesamtverzeichnis][Seitenübersicht]

  automatisch erstellt am 23.10.2009