Elementaire combinatoriek: Faculteit en binomiaalcoëfficiënt
Faculteit
Net zo goed als je \(\blue{ \overbrace{\color{black}{a \times a \times \cdots \times a}}^{n\mathrm{\;maal}}}\) verkort to \(a^n\), heb je ook een verkorte notaite voor \(n\cdot (n-1)\cdots 3\cdot 2\cdot 1\), namelijk \(n!\). We spreken dit uit als ``\(n\) faculteit''.
De faculteit van een natuurlijk getal \(n\) is als volgt gedefinieerd: \[\begin{cases} n! =n\cdot (n-1)\cdots 3\cdot 2\cdot 1 & \text{voor } n\in\mathbb{N}\backslash\{0\}\\ 0!=1&\end{cases}\]
We kunnen de faculteit ook via een oneigenlijke integraal definiëren in de gedaante van de gammafunctie: \[\Gamma(x)=\int_{0}^{\infty} t^{x-1}e^{-t}\,\dd t\] Voor natuurlijke getallen \(n\) geldt dan: \[n!=\Gamma(n+1)\] Maar omdat de gammafunctie voor alle getallen uitgezonderd de negatieve gehele getallen bestaat, kun je dus ook de faculteit uitbreiden tot meer dan alleen de natuurlijke getallen. Bijvoorbeeld: \[\begin{aligned} (-\tfrac{1}{2})! &= \Gamma(\tfrac{1}{2})\\[0.25cm] &= \int_{0}^{\infty} t^{-\frac{1}{2}}e^{-t}\,\dd t\\[0.25cm] &=2\cdot \int_{0}^{\infty} e^{-u^2}\,\dd u & \blue{\text{substitutie }u=t^{\frac{1}{2}}\text{ en } \dd u=t^{-\frac{1}{2}}\,\dd t}\\[0.25cm] &= 2\cdot \frac{\sqrt{\pi}}{2} & \blue{\text{standaardintegraal}}\\[0.25cm] &= \sqrt{\pi}\end{aligned}\] De grafiek van de faculteitsfunctie ziet er als volgt uit:
Toepassing 1 Het aantal manieren waarop \(n\) verschillende objecten gerangschikt kunnen worden is gelijk aan \(n!\).
Anders gezegd, het aantal permutaties van \(n\) verschillende dingen (ofwel het aantal rangschikkingen van \(n\) dingen) is gelijk aan \(n!\).
Toepassing 2 Het aantal permutaties van \(n\) dingen waarvan er \(m\) gelijk zijn en de rest verschillend zijn is gelijk aan \(\dfrac{n!}{m!}\).
Eigenschappen Voor alle \(m,n\in\mathbb{N}\) met \(m<n\) gelden de volgende regels: \[\begin{aligned} n!&=n\cdot (n-1)!\\[0.25cm] \frac{n!}{m!} &= (m+1)\cdot (m+2)\cdots (n-1)\cdot n\end{aligned}\]
