Elementaire combinatoriek: Faculteit en binomiaalcoëfficiënt
Eigenschappen van binomiaalcoëfficiënten
Uit de definitie van de binomiaalcoëfficiënt \(\binom{n}{k}\) volgen de volgende eigenschappen.
Eigenschappen Voor natuurlijke getallen \(n\), \(k\) met \(k\le n\) geldt: \[\begin{aligned}\binom{n}{k} &= \binom{n}{n-k}\\[0.25cm] \binom{n}{k} &= \frac{n}{k}\binom{n-1}{k-1}\quad\text{voor }k\ge 1 \\[0.25cm] \binom{n}{0}&=\binom{n}{n}=1\\[0.25cm] \binom{n}{1}&=n\quad\text{voor }n\ge 1\\[0.25cm] \binom{n}{2}&=\tfrac{1}{2}n(n-1)\quad\text{voor }n\ge 2\\[0.25cm] \binom{n+1}{k}&= \binom{n}{k-1}+\binom{n}{k}\quad\text{voor }k\ge 1 \end{aligned}\]
De laatste gelijkheid \[\binom{n+1}{k}= \binom{n}{k-1}+\binom{n}{k}\quad\text{voor }k\ge 1\] kan geïnterpreteerd worden als een recursieve formule waarmee binomiaalcoëfficiënten berekend kunnen worden. Dit leidt tot de driehoek van Pascal.
Driehoek van Pascal In de driehoek van Pascal staan getallen vermeld in een piramidevorm: \[\blue{\begin{array}{lccccccccccccc}
n=0\rightarrow\phantom{abc} &&&&&&&1&&&&&&\\[0.2cm]
n=1\rightarrow\phantom{abc} &&&&&&1&&1&&&&&\\[0.2cm]
n=2\rightarrow\phantom{abc} &&&&&1&&2&&1&&&&\\[0.2cm]
n=3\rightarrow\phantom{abc} &&&&1&&3&&3&&1&&&\\[0.2cm]
n=4\rightarrow\phantom{abc} &&&1&&4&&6&&4&&1&&\\[0.2cm]
n=5\rightarrow\phantom{abc} &&1&&5&&10&&10&&5&&1&\\[0.2cm]
n=6\rightarrow\phantom{abc} &1&&6&&15&&20&&15&&6&&1\\[0.2cm]
\ldots &&&&&&&\ldots&&&&&&&
\end{array}}\] Langs de linker- en rechterkant staan enen en verder is elk getal de som van zijn linker- en rechterbovenbuur.
Dit betekent dat in de \(n\)-de rij op plek \(k=0,\ldots, n\) de binomiaalcoëfficiënt \(\binom{n}{k}\) staat.
Bijvoobeeld, \(\binom{6}{0}=\binom{6}{6}=1\), \(\binom{6}{2}=15\) en \(\binom{6}{3}=20\).
