Combinatoriek

Permutaties van drie gekleurde elementen

Combinatoriek of combinatieleer is een tak van de wiskunde. In de combinatoriek bestudeert men eindige verzamelingen van objecten die aan bepaalde eigenschappen voldoen. Men houdt zich in het bijzonder bezig met het tellen van objecten in deze verzamelingen. Aangezien combinatoriek vooral over tellen gaat, wordt het wel de 'kunst van het tellen' genoemd.

Vaasmodel

Een aantal telproblemen kan worden opgelost met behulp van een vaasmodel[1]. Uit een vaas met n {\displaystyle n} (verschillende) knikkers worden k {\displaystyle k} knikkers gehaald (getrokken). We kunnen de getrokken knikker weer terugleggen of niet en we kunnen van de getrokken k {\displaystyle k} knikkers de volgorde onthouden of niet. We spreken over trekken met of zonder terugleggen en van geordende of ongeordende uitkomst (de volgorde is wel of niet van belang).

Variatie

We trekken k {\displaystyle k} keer uit een verzameling van n {\displaystyle n} elementen, zonder terugleggen en onthouden de volgorde. Voor de eerste trekking zijn er n {\displaystyle n} mogelijkheden. Voor elke volgende trekking is er steeds één mogelijkheid minder dan voor de vorige. Een getrokken rijtje heet een variatie. Daarvan zijn er

V ( n , k ) = n ! ( n − k ) ! {\displaystyle V(n,k)={\frac {n!}{(n-k)!}}}

Voorbeeld: vier vrienden hebben iets te vieren en ze hebben een complete zaal gehuurd. Er zijn 200 plaatsen en ze gaan zo maar ergens zitten. Hoeveel mogelijkheden zijn er?

200 ! ( 200 − 4 ) ! = 200 × 199 × 198 × 197 {\displaystyle {\frac {200!}{(200-4)!}}=200\times 199\times 198\times 197}

Als we alle n {\displaystyle n} elementen trekken, dus als k = n , {\displaystyle k=n,} krijgen we een mogelijke manier om de n {\displaystyle n} elementen van de verzameling op volgorde te zetten. Zo'n volgorde heet een permutatie. Daarvan zijn er

n ⋅ ( n − 1 ) ⋅ … ⋅ 2 ⋅ 1 = n ! {\displaystyle n\cdot (n-1)\cdot \ldots \cdot 2\cdot 1=n!}

Voorbeeld: De 52 kaarten van een kaartspel kunnen zonder terugleggen op 52! mogelijkheden worden getrokken.

Herhalingsvariatie

We trekken k {\displaystyle k} keer uit een verzameling van n {\displaystyle n} elementen, met terugleggen en onthouden de volgorde. Voor elk van de k {\displaystyle k} trekkingen zijn er n {\displaystyle n} mogelijkheden. Een getrokken rijtje heet een herhalingsvariatie. Daarvan zijn er

n k {\displaystyle n^{k}}

Voorbeeld: Er zijn 10 4 = 10.000 {\displaystyle 10^{4}=10.000} verschillende pincodes.

Combinatie

We trekken k {\displaystyle k} keer uit een verzameling van n {\displaystyle n} elementen, zonder terugleggen en letten niet op de volgorde. Een getrokken k {\displaystyle k} -tal heet een combinatie. We kunnen eerst wel op de volgorde letten en die daarna vergeten. Er zijn dan k ! {\displaystyle k!} variaties die hetzelfde k {\displaystyle k} -tal opleveren. Het aantal verschillende combinaties is dus:

( n k ) = n ! k ! ( n − k ) ! {\displaystyle {n \choose k}={n! \over k!(n-k)!}}

Voorbeeld: Hoeveel verschillende ploegen van 3 deelnemers kunnen we vormen uit 10 deelnemers. Dat zijn er

( 10 3 ) = 10 ! 3 ! 7 ! = 120 {\displaystyle {\binom {10}{3}}={\frac {10!}{3!7!}}=120}

Herhalingscombinatie

We trekken k {\displaystyle k} keer uit een verzameling van n {\displaystyle n} elementen, met terugleggen en letten niet op de volgorde. Een getrokken k {\displaystyle k} -tal heet een herhalingscombinatie. We kunnen zo'n k {\displaystyle k} -tal beschrijven door van elk van de n {\displaystyle n} elementen aan te geven hoe vaak het gekozen is. Dit kan aanschouwelijk gebeuren door voor elk element net zoveel 0-en te schrijven als het gekozen is en tussen de 0-en van de verschillende elementen een 1 als scheiding te schrijven. Het aantal verschillende herhalingscombinaties is dan het aantal mogelijke rijtjes bestaande uit k {\displaystyle k} keer een 0 en n − 1 {\displaystyle n-1} keer een 1. We moeten van de k + n − 1 {\displaystyle k+n-1} plaatsen in de rij er k {\displaystyle k} aanwijzen waar een 0 komt te staan. Het aantal is dus net zoveel als het aantal combinaties van k {\displaystyle k} uit k + n − 1 : {\displaystyle k+n-1:}

( k + n − 1 k ) = ( k + n − 1 ) ! k ! ( n − 1 ) ! {\displaystyle {k+n-1 \choose k}={(k+n-1)! \over k!(n-1)!}}

Voorbeeld: Op hoeveel manieren kun je 5 eieren kleuren als je over 3 kleuren beschikt. Dus k = 5 {\displaystyle k=5} en n = 3. {\displaystyle n=3.} Dat kan dus op

( 5 + 3 − 1 5 ) = 7 ! 5 ! 2 ! = 21 {\displaystyle {5+3-1 \choose 5}={7! \over 5!2!}=21}

manieren.

Toepassing

Voorbeeld: Bereken op de volgende manier op hoeveel manieren n {\displaystyle n} gelijke knikkers over k {\displaystyle k} verschillende bakjes kunnen worden verdeeld, zodat geen bakje leeg blijft.

Doe in elk bakje alvast een knikker. Er blijven er n − k {\displaystyle n-k} over. Deze worden nog over de bakjes verdeeld via een herhalingscombinatie, dus van n − k {\displaystyle n-k} uit k {\displaystyle k} , voor ieder van de resterende knikkers wordt bepaald in welk bakje hij komt. Er zijn dus:

( n − 1 n − k ) = ( n − 1 k − 1 ) {\displaystyle {n-1 \choose n-k}={n-1 \choose k-1}}

mogelijkheden.

Voetnoten
  1. ↑ Kansrekening, het zekere van het onzekere. H.G. Dehling en J.N. Kalma, Epsilon Uitgaven, Utrecht ISBN 90-5041-092-8
Mediabestanden
Zie de categorie Combinatorics van Wikimedia Commons voor mediabestanden over dit onderwerp.