Binomiaalcoëfficiënt

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
De binomiaalcoëfficiënten zijn de invoerwaarden in de driehoek van Pascal.

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

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

en

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

Voorbeeld[bewerken]

Als voorbeeld rekenen we uit hoeveel kleurencombinaties er mogelijk zijn als we uit de zeven kleuren van de regenboog er drie mogen kiezen. De volgorde waarin we de kleuren kiezen is niet van belang.

Volgens deze berekening zijn er {7 \choose 3}=\frac{7!}{3!4!}=35 combinaties mogelijk van drie verschillende kleuren gekozen uit de zeven van de regenboog.

Hoe komt men tot de waarde van deze coëfficiënt? Voor de eerste kleurkeuze zijn er 7 mogelijkheden, voor de tweede nog 6, en voor de derde nog 5. Samen dus 7\times 6\times 5 mogelijkheden, ofwel meer algemeen n!/(n-k)!. Maar nu is de volgorde van de kleuren wel belangrijk: we kunnen eerst rood en dan geel hebben gekozen, maar ook eerst geel en dan rood. Om dit eruit te halen moeten we nog delen door het aantal volgordes van de drie kleuren, dat is 1\times 2\times 3 of meer algemeen k!. De gehele binomiaalcoëfficiënt komt dus uit op n!/(k!(n-k)!).

Driehoek van Pascal[bewerken]

Het combinatorische karakter van de binomiaalcoëfficiënten leidt tot de volgende eigenschap:

{n\choose k}={n-1\choose k-1}+{n-1 \choose k},

die zich gemakkelijk laat begrijpen door van de n objecten er 1 apart te leggen en uit de overige n-1 er k-1 te kiezen en deze aan te vullen met die ene of alle k uit de n-1 overige te kiezen.

De bovenstaande recursieve formule laat zich fraai weergeven in de zgn. driehoek van Pascal (zie aldaar).

Eigenschappen[bewerken]

Als n een natuurlijk getal is, dan geldt

 \binom n k \equiv 0 \pmod{n} voor alle 0 < k < n
dan en slechts dan als
n is priem.

We kunnen dit als volgt bewijzen: Wanneer p een priemgetal is, deelt p

 \binom p k = \frac{p \cdot (p-1) \cdots (p-k+1)}{k \cdot (k-1) \cdots 1} voor alle 0 < k < p

omdat het een natuurlijk getal is en de teller een priemfactor p heeft, maar de noemer geen priemfactor p heeft. Dus  \tbinom p k ≡0 (mod p).

Wanneer n samengesteld is, neem dan de kleinste priemfactor van n, noem die p. Laat bovendien k = n/p. Dan is 0 < p < n en

 \binom n p = \frac{n(n-1)(n-2)\cdot...\cdot(n-p+1)}{p!}=\frac{k(n-1)(n-2)\cdot...\cdot(n-p+1)}{(p-1)!}\not\equiv 0 \pmod{n}

anders zou de teller k(n−1)(n−2)×...×(np+1) deelbaar zijn door n = k×p. Dit kan alleen het geval zijn wanneer (n−1)(n−2)×...×(np+1) deelbaar is door p. Maar n is deelbaar door p, dus p deelt n−1, n−2, ... en np+1 niet. En omdat p priem is, weten we dat p het product (n−1)(n−2)×...×(np+1) niet deelt en dus kan de teller niet deelbaar zijn door n.

Toepassing[bewerken]

De binomiaalcoëfficiënten vinden toepassing in onder andere het binomium van Newton en in de kansrekening bij de binomiale verdeling.

Externe link[bewerken]