Binomiaalcoëfficiënt

Elementaire combinatoriek: Faculteit en binomiaalcoëfficiënt

Binomiaalcoëfficiënt

De binomiaalcoëfficiënt $\boldsymbol{n}$ boven $\boldsymbol{k}$ , genoteeerd als $\binom{n}{k}$ , van twee natuurlijke getallen $n$ en $k$ met $k\le n$ is gedefinieerd als $\binom{n}{k}=\frac{n!}{k!\,(n-k)!}$

Een binomiaalcoëfficiënt reken je nooit uit door de drie faculteiten in de definitie afzonderlijk te berekenen. Met de eigenschappen van de faculteit kun je de grootste van de twee faculteiten in de noemer wegdelen tegen het beginstukvan $n!$ . Een voorbeeld: $\begin{aligned}\binom{8}{3}&=\frac{8!}{3!\cdot 5!}\\[0.25cm] &=\frac{8\times 7\times 6\times \cancel{5}\times \cancel{4}\times \cancel{3}\times \cancel{2}\times \cancel{1}}{(3\times 2\times 1)\times(\cancel{5}\times \cancel{4}\times \cancel{3}\times \cancel{2}\times \cancel{1})}\\[0.25cm] &= \frac{8\times 7\times 6}{3\times 2\times 1}\\[0.25cm] &=8\times 7\\[0.25cm] &=56\end{aligned}$ In het algemeen: $\binom{n}{k}=\frac{n (n-1)\cdots (n-k+1)}{k!}$

Als generalisatie van $\binom{n}{k}=\frac{n!}{k!\cdot (n-k)!}=\frac{n(n-1)\cdots (n-k+1)}{k!}$ definieert men voor willekeurige getallen $x$ en $k\in\mathbb{N}$ $\binom{x}{k}=\frac{x (x-1)\cdots (x-k+1)}{k!}$ Dan geldt bijvoorbeeld (reken na!): $\binom{-1}{k}=(-1)^k\qquad\text{en}\qquad \binom{k-1}{k}=0$ voor alle $k\in\mathbb{N}$ .

Het aantal manieren waarom men uit $n$ verschillende objecten er zonder terugleggen $k$ kan kiezen en waarbij de volgorde van kiezen geen rol speelt is gelijk aan de binomiaalcoëfficiënt $\binom{n}{k}$ . Zo'n mogelijke keuze heet combinatie, trekking of greep. Kortweg zeggen we dat het aantal combinaties van $\boldsymbol{k}$ uit $\boldsymbol{n}$ gelijk is aan $\binom{n}{k}$ . Dit jargon verklaart ook de alternatieve notaties $C^n_k$ en ${}^{n}C_{k}$ , alsmede en de naam van de rekenmachineknop/functie nCr om het aantal combinaties van $r$ uit $n$ te berekenen.

Het aantal manieren waarom men uit $n$ verschillende objecten er zonder terugleggen $k$ kan kiezen maar waarbij wel de volgorde van kiezen een rol speelt is gelijk aan $\binom{n}{k}\cdot k! = \dfrac{n!}{(n-k)!}= n(n-1)\cdots (n-k+1)\text.$ We noemen dit ook wel het aantal variaties van $\boldsymbol{k}$ uit $\boldsymbol{n}$ .

Het aantal manieren waarom men uit $n$ verschillende objecten er $k$ kan kiezen maar wel na elke trekking het gekozen object wordt teruggelegd en de volgorde van kiezen geen rol speelt is gelijk aan $\binom{n+k-1}{k}$ . We noemen dit ook wel het aantal herhalingscombinaties van $\boldsymbol{k}$ uit $\boldsymbol{n}$ .

Voor de volledigheid vermelden we dat het aantal manieren waarom men uit $n$ verschillende objecten er $k$ kan kiezen maar wel na elke trekking het gekozen object wordt teruggelegd en de volgorde van kiezen wel een rol speelt is gelijk aan $n^k$ . We noemen dit ook wel het aantal herhalingsvariaties van $\boldsymbol{k}$ uit $\boldsymbol{n}$ .