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 {n}{k}}={\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}$