Binomiaalcoëfficiënt
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,3}
- {1,4}
- {1,5}
- {1,6}
- {2,1}
- {2,2}
- {2,3}
- {2,4}
- {2,5}
- {2,6}
- {3,1}
- {3,2}
- {3,3}
- {3,4}
- {3,5}
- {3,6}
- {4,1}
- {4,2}
- {4,3}
- {4,4}
- {4,5}
- {4,6}
- {5,1}
- {5,2}
- {5,3}
- {5,4}
- {5,5}
- {5,6}
- {6,1}
- {6,2}
- {6,3}
- {6,4}
- {6,5}
- {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