Binomialkoeffizient

Grundbegriffe

Binomialkoeffizient oder Eulersches Symbol

Der Binomialkoeffizient oder Eulersches Symbol ${n \choose k}$, man liest dieses Symbol: "$n$ über $k$", wird im Rahmen der Kombinatorik verwendet.

Seien $n,k\in \mathbb{N}$ mit $n\geq k$, dann ist der Binomialkoeffizient definiert als:

$\binom nk = \frac{n!}{k! \cdot (n-k)!}$

Zusatzinformationen

Spezialfälle

${n \choose 0}$	$\, =$	$\frac{n\,!}{0\,! (n-0)\,!}$	$\, = 1$
${n\choose 1 }$	$\, =$	$\frac{n\,!}{1\,! (n-1)\,!}$	$\, = n$
${ 0 \choose 0}$	$\, =$	${ n \choose n }$	$\, = 1$
${ n\choose k }$	$\, =$	$\, 0,$	wenn $k > n \geq 0$

Symmetrie-Eigenschaft

${ n \choose k } = {n \choose n-k }$

Begründung der Symmetrie-Eigenschaft:

$\frac{n\,!}{k\,! (n-k)\,!} = \frac{n\,!}{(n-k)\,! (n-(n-k))\,!}$

Summen-Eigenschaft

${n\choose k} + {n \choose k + 1}= {n + 1\choose k + 1 }$

Herleitung der Summen-Eigenschaft:

$\frac{n\,!}{k\,! (n-k)\,!} + \frac{n\,!}{(k+1)\,! (n-(k+1))\,!}$	$\,=$	$\frac{(k+1)n\,!}{(k+1)k\,! (n-k)\,!} + \frac{(n-k)n\,!}{(k+1)\,! (n-(k+1))\,! (n-k)}$
	$\, =$	$\frac{n\,!((k+1) + (n-k))}{(k+1)\,! (n-k)\,!}$
	$\, =$	$\frac{n\,! (n+1)}{((n+1) - (k+1))\,! (k+1)\,!}$
	$\, =$	$\frac{(n+1)\,!}{((n+1) - (k+1))\,! (k+1)\,!}$
	$=$	${ n+1\choose k+1 }$