title: Combinatoriek
text: Combinatoriek of combinatieleer is een tak van de wiskunde. In de combinatoriek bestudeert men eindige verzamelingen van objecten die aan gespecificeerde eigenschappen voldoen. In het bijzonder houdt men zich bezig met het "tellen" van objecten in deze verzamelingen en het bepalen of er zekere "optimale" objecten in een verzameling aanwezig zijn. 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. Uit een vaas met  (verschillende) knikkers worden  knikkers gehaald (getrokken). We kunnen de getrokken knikker weer terugleggen of niet en we kunnen van de getrokken  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).
  
  {| border="1" width="90%"
  |-
  |
   Variatie 
  
  We trekken  keer uit een verzameling van  elementen, zonder terugleggen en onthouden de volgorde. Voor de eerste trekking zijn er  mogelijkheden. Voor elke volgende trekking is er steeds één mogelijkheid minder dan voor de vorige. Een getrokken rijtje heet een variatie. Daarvan zijn er
  
  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?
  
  Als we alle  elementen trekken, dus als  krijgen we een mogelijke manier om de  elementen van de verzameling op volgorde te zetten. Zo'n volgorde heet een permutatie. Daarvan zijn er
  
  Voorbeeld: we sorteren een pak kaarten (trekken 52 kaarten uit het pak); er zijn dan 52! mogelijkheden
  |}
  
  {| border="1" width="90%"
  |-
  |
   Herhalingsvariatie 
  
  We trekken  keer uit een verzameling van  elementen, met terugleggen en onthouden de volgorde. Voor elk van de  trekkingen zijn er  mogelijkheden. Een getrokken rijtje heet een herhalingsvariatie. Daarvan zijn er
  
  Voorbeeld: Hoeveel pincodes zijn er? Men kiest 4 maal uit 10 cijfers dus 
  |}
  
  {| border="1" width="90%"
  |-
  |
   Combinatie 
  
  We trekken  keer uit een verzameling van  elementen, zonder terugleggen en letten niet op de volgorde. Een getrokken -tal heet een combinatie. We kunnen eerst wel op de volgorde letten en die daarna vergeten. Er zijn dan  variaties die hetzelfde -tal opleveren. Het aantal verschillende combinaties is dus:
  
  Voorbeeld: Hoeveel verschillende ploegen van 3 deelnemers kunnen we vormen uit 10 deelnemers. Dat zijn er
  .
  |}
  
  {| border="1" width="90%"
  |-
  |
   Herhalingscombinatie 
  
  We trekken  keer uit een verzameling van  elementen, met terugleggen en letten niet op de volgorde. Een getrokken -tal heet een herhalingscombinatie. We kunnen zo'n -tal beschrijven door van elk van de  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  keer een 0 en  keer een 1. We moeten van de  plaatsen in de rij er  aanwijzen waar een 0 komt te staan. Het aantal is dus net zoveel als het aantal combinaties van  uit 
  
  Voorbeeld: Op hoeveel manieren kun je 5 eieren kleuren als je over 3 kleuren beschikt. Dus  en  Dat kan dus op
  
  manieren.
  |}
  
  Toepassing
  Op hoeveel manieren kunnen  gelijke knikkers verdeeld worden over  verschillende bakjes, zo, dat geen bakje leeg is?
  
  Doe in elk bakje alvast een knikker. Er blijven er  over. Deze worden nog over de bakjes verdeeld via een herhalingscombinatie, dus van  uit  voor elk van de resterende knikkers wordt bepaald in welk bakje hij komt. Er zijn dus:
  
  mogelijkheden.
  
  Referenties
  
   
  Discrete wiskunde