Binomiaalcoëfficiënt

Een binomiaalcoëfficiënt, geschreven als

${\displaystyle {\binom {n}{k}}}$, spreek uit ${\displaystyle n}$ boven ${\displaystyle k}$ of ${\displaystyle n}$ over ${\displaystyle k}$

is een grootheid uit de combinatoriek die aangeeft op hoeveel manieren men uit ${\displaystyle n}$ verschillende objecten er zonder terugleggen ${\displaystyle k}$ kan kiezen. Zo'n mogelijke keuze heet een combinatie of greep. Een binomiaalcoëfficiënt is gedefinieerd als het natuurlijke getal:

${\displaystyle {n \choose k}={\frac {n!}{k!\ (n-k)!}}\quad {\mbox{voor }}0\leq k\leq n}$

en

${\displaystyle {n \choose k}=0\quad {\mbox{voor }}k<0{\mbox{ of }}k>n}$

Omdat de keuze van ${\displaystyle k}$ objecten uit ${\displaystyle n}$ ook kan worden opgevat als de keuze ${\displaystyle n-k}$ objecten, eigenlijk de niet-gekozen objecten, moet ${\displaystyle {\tbinom {n}{k}}}$ gelijk zijn aan ${\displaystyle {\tbinom {n}{n-k}}}$. Inderdaad volgt uit de definitie:

${\displaystyle {n \choose k}={\frac {n!}{k!\ (n-k)!}}={\frac {n!}{(n-k)!\ k!}}={\binom {n}{n-k}}}$

De naam binomiaalcoëfficiënt verwijst naar het resultaat van een macht van een tweeterm, een binoom is een tweeterm. Binoom komt ook in binomium van Newton voor. Blaise Pascal schreef in zijn correspondentie met Pierre de Fermat in 1654 over de berekeningen, die hij hiervoor had uitgevoerd.^[1]

Als andere notatie voor de binomiaalcoëfficënt ${\displaystyle {\tbinom {n}{k}}}$ komen voor: ${\displaystyle C(n,k),\ _{n}\!C_{k},\ ^{n}\!C_{k},C_{k}^{n},C_{n}^{k}}$ en ${\displaystyle C_{n,k}}$, waarin de ${\displaystyle C}$ staat voor de Engelse woorden 'combination' of 'choice'. Dat wordt op sommige rekenmachines met ${\displaystyle {\text{nCk}}}$ of ${\displaystyle {\text{nCr}}}$ aangegeven.

Berekening

Er zijn ${\displaystyle n(n-1)\ldots (n-k+1)=n!/(n-k)!}$ mogelijkheden om ${\displaystyle k}$ objecten op volgorde uit ${\displaystyle n}$ verschillende te kiezen zonder terugleggen. Van elk gekozen ${\displaystyle k}$-tal zijn er ${\displaystyle k!}$ mogelijke volgordes. De binomiaalcoëfficiënt is dus ${\displaystyle {\frac {n!}{k!\ (n-k)!}}}$.

Voorbeeld

Het aantal kleurencombinaties dat mogelijk is bij een keuze van drie kleuren uit de zeven kleuren van de regenboog, waarbij de volgorde van de kleuren niet van belang is, is

${\displaystyle {7 \choose 3}={\frac {7!}{3!\ 4!}}=35}$

Voor de eerste kleur die wordt gekozen zijn er 7 mogelijkheden, voor de tweede nog 6 en voor de derde nog 5. In totaal dus ${\displaystyle 7\times 6\times 5=7!/4!}$ mogelijkheden, maar daarbij is rekening gehouden met de volgorde van de kleuren. Om van deze volgorde af te zien, moet nog door het aantal volgordes van de drie kleuren worden gedeeld, dus door ${\displaystyle 1\times 2\times 3=3!}$

Eigenschappen

• ${\displaystyle {n \choose k}={n-1 \choose k-1}+{n-1 \choose k}}$,

De driehoek van Pascal wordt aan de hand van deze recursieve formule samengesteld.

• Voor een priemgetal ${\displaystyle p}$ is de binomiaalcoëfficiënt ${\displaystyle {\binom {p}{k}}}$ voor alle ${\displaystyle 0<k<p}$ een veelvoud van ${\displaystyle p}$. Dit is te begrijpen aangezien

${\displaystyle {\binom {p}{k}}={\frac {p(p-1)\ldots (p-k+1)}{k(k-1)\ldots 1}}}$,

voor alle ${\displaystyle 0<k<p}$, een natuurlijk getal is en de teller wel een priemfactor ${\displaystyle p}$ heeft, maar de noemer niet.

• Als omgekeerd voor een natuurlijke ${\displaystyle n}$ de binomiaalcoëfficiënt ${\displaystyle {\binom {n}{k}}}$ voor alle ${\displaystyle 0<k<n}$ een veelvoud van ${\displaystyle n}$ is, is ${\displaystyle n}$ een priemgetal.

Bewijs 

Het bewijs is een bewijs uit het ongerijmde. Veronderstel dat ${\displaystyle n}$ samengesteld is. Noem ${\displaystyle p}$ de kleinste priemfactor van ${\displaystyle n}$ en ${\displaystyle k=n/p}$.

Dan is ${\displaystyle 0<p<n}$ en is

${\displaystyle {\binom {n}{p}}={\frac {n(n-1)(n-2)\ldots (n-p+1)}{p!}}={\frac {k(n-1)(n-2)\ldots (n-p+1)}{(p-1)!}}}$

Veronderstel dat ${\displaystyle {\binom {n}{p}}}$ een veelvoud van ${\displaystyle n}$ is, dan kan de teller ${\displaystyle k(n-1)(n-2)\ldots (n-p+1)}$ door ${\displaystyle n=k\ p}$ worden gedeeld.

Dit kan alleen als het product ${\displaystyle (n-1)(n-2)\ldots (n-p+1)}$ door ${\displaystyle p}$ kan worden gedeeld.

${\displaystyle p}$ is een priemgetal en ${\displaystyle n}$ kan door ${\displaystyle p}$ worden gedeeld. Geen van de factoren uit het product ${\displaystyle (n-1)(n-2)\ldots (n-p+1)}$ kan door ${\displaystyle p}$ worden gedeeld, dus het product zelf ook niet.

Dat geeft een tegenspraak, dus moet ${\displaystyle n}$ een priemgetal zijn.

Toepassing

De binomiaalcoëfficiënten vinden toepassing in onder andere het binomium van Newton en in de kansrekening bij de binomiale verdeling. De coëfficiënt van de ${\displaystyle k}$-de macht van ${\displaystyle x}$ in bijvoorbeeld het polynoom ${\displaystyle (1+x)^{n}}$ is de binomiaalcoëfficënt ${\displaystyle {\tbinom {n}{k}}}$:

${\displaystyle (1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}}$