Binomiaalcoëfficiënt

Uit De Vliegende Brigade
Ga naar: navigatie, zoeken
Binomiaalcoëfficiënten komen voort uit de driehoek van Pascal

Een binomiaalcoëfficiënt is een concept uit de combinatoriek. Het geeft aan hoeveel subsets (zonder teruglegging, zonder specifieke volgorde) met k elementen je kunt maken uit een set met n elementen

Definitie

Spreek uit n over k:

(n)       n!
( ) = ---------   voor 0 =< k =< n
(k)   k!(n-ik)!

Calc

In Calc bereken je faculteiten met de functie fact. Bv:

=fact(6)

Binomiaalcoëfficiënten berken je middels combin. Bv.:

=combin(6;4)

Voorbeeld: Twee keer dobbelen

Hoeveel combinaties van 2 cijfers kun je gooien met een dobbelsteen? Volgorde maakt hierbij niet uit.

Door het op te sommen, komen we uit op 36 combinaties:

  1. {1,1}
  2. {1,2}
  3. {1,3}
  4. {1,4}
  5. {1,5}
  6. {1,6}
  7. {2,1}
  8. {2,2}
  9. {2,3}
  10. {2,4}
  11. {2,5}
  12. {2,6}
  13. {3,1}
  14. {3,2}
  15. {3,3}
  16. {3,4}
  17. {3,5}
  18. {3,6}
  19. {4,1}
  20. {4,2}
  21. {4,3}
  22. {4,4}
  23. {4,5}
  24. {4,6}
  25. {5,1}
  26. {5,2}
  27. {5,3}
  28. {5,4}
  29. {5,5}
  30. {5,6}
  31. {6,1}
  32. {6,2}
  33. {6,3}
  34. {6,4}
  35. {6,5}
  36. {6,6}

In detail:

  • Voor de eerste worp hebben we 6 mogelijkheden
  • Voor de tweede worp hebben we opnieuw 6 mogelijkheden
  • ---
  • 6*6 = 36

Hierbij hebben we geen binomiaalcoëfficienten nodig! Die spelen pas een rol, wanneer je een experiment doet zonder teruglegging.

Voorbeeld: Dobbelsteen (2)

Om het voorbeeld hiervoor geschikt te maken voor gebruik met binomiaalcoëfficiënten: Hoe veel combinaties kun je maken als elk cijfer maar 1 keer gegooid mag worden?

  • Voor het eerste cijfer hebben we 6 keuzes
  • Voor het tweede cijfer hebben we 5 keuzes
  • Da's 6!/4!
  • Omdat volgorde niet uitmaakt, moeten we het resultaat delen door het aantal mogelijke volgordes per set, en da's 2@
  • 6!/4!2! = 15

Direct berekend mbv. binomiaalcoëfficiënten:

(6)       6!     720
( ) = -------- = ---- = 15
(2)   2!(6-2)!    48

Voorbeeld: Regenboog

De regenboog heeft 7 kleuren. Hoeveel combinaties van 3 kleuren kun je maken?

(7)    7!
( ) = ---- = 35
(3)   3!4!

In detail:

  • Voor de eerste kleur zijn er 7 keuzes
  • Voor de tweede kleur zijn er 6 keuzes
  • Voor de derde kleur zijn er 5 keuzes
  • -----------------------------------------
  • 7*6*5
  • = (7*6*5)*(4*3*2*1)/(4*3*2*1)
  • = 7!/4!
  • = 5040/24 = 210 (tussenresultaat)
  • Echter, hierbij wordt aangenomen dat de volgorde van belang is. Dus rood-geel-blauw is iets anders dan geel-rood-blauw. De volgorde is hier echter niet van belang. Een set van 3 elementen kan in 3! volgordes voorkomen. Dus het eindresultaat moet hierdoor gedeeld worden:
  • 210/3! = 35.

Driehoek van Pascal

Er geldt:

(n)   (n-1)   (n-1)
(k) = (k-1) + ( k )

Met deze recursieve formulie beland je snel bij de driehoek van Pascal.

(4)   
(2) = 4!/2!2! = 24/4 = 6
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
De eerste 11 rijen van de driehoek van Pascal

Bronnen