Permutaties en Combinaties (4/4) In de dierentuin Een dierentuin wordt ingericht. Er is aanvankelijk plaats voor 10 dieren, te kiezen zijn apen (A), beren (B), chinchilla's (C) en dromedarissen (D). Hoeveel dierentuinen zijn mogelijk? Twee dierentuinen zijn ongelijk als ze verschillende dieren bevatten in soort of aantal. De plaatsing van de hokken is daarbij niet van belang. Dit is een ander type probleem dan we hiervoor zagen. Het verband met permutaties en combinaties ligt zelfs niet voor de hand. We coderen een dierentuin met een letterrijtje. En omdat de volgorde waarin de dieren worden gekozen onbelangrijk is, sorteren we ze op alfabet. Mogelijke dierentuinen zijn: - AAABBBCCDD - AAAABBBBDD - CCCDDDDDDD - AAAAAAAAAA en nog heel wat meer. Truc: tussen verschillende dieren plaatsen we een hek (H). De dierentuinen van hiervoor zien er dan zo uit: - AAAHBBBHCCHDD - AAAAHBBBBHHDD - HHCCCHDDDDDDD - AAAAAAAAAAHHH Er zijn 3 hekken geplaatst tussen de 4 diersoorten. Links van hek 1 de apen, tussen hek 1 en 2 de beren, rechts van hek 2 de chinchilla's en rechts van hek drie de dromedarissen. Als twee hekken tegen elkaar staan wil dat zeggen, dat er van dit type dier geen enkele is gekozen. Door de plaatsing van de hekken staat de diersoort vast, dus kunnen we voor elk dier wel een x invoeren. De rijtjes hiervoor worden : - xxxHxxxHxxHxx - xxxxHxxxxHHxx - HHxxxHxxxxxxx - xxxxxxxxxxHHH Er zijn dus evenveel dierentuinen te maken als er 3 hekken op 13 plaatsen zijn neer te zetten. Algemeen: Als er N verschillende diersoorten zijn, dan moeten (N-1) hekken worden geplaatst. Kiezen we dan k dieren, dan kunnen die (N-1) hekken op (N - 1 + k) plaatsen worden neergezet. Het aantal verschillende dierentuinen is dan het aantal combinaties van (N-1) uit (N-1+k) dat is: ( N - 1 + k N - 1 ) voorbeelden 1. Hoeveel getallen van 5 cijfers kan je maken, als de volgorde van de cijfers niet van belang is? Elk cijfer mag meermalen worden gekozen, de volgorde is onbelangrijk, dus dit is een 'dierentuinen' probleem met N = 10 en k = 5. antwoord: ( 10 - 1 + 5 10 - 1 ) = 2002 2. Op hoeveel manieren kan je 12 paaseieren verven als per ei uit zes kleuren kan worden gekozen? Ook hier: volgorde van schilderen niet van belang, elke kleur meermalen te kiezen,dus ook 'dierentuinen' probleem, met N = 6 en k = 12. antwoord: ( 6 - 1 + 12 6 - 1 ) = 6188 Voor de volledigheid Hoeveel getallen van 6 cijfers zijn er in het 10 tallig stelsel? Voor elk cijfer is er de keus uit 10, de volgorde van kiezen is van belang en het antwoord is 106 voorbeeld Een kantoorgebouw telt 8 verdiepingen. Op de begane grond stappen 10 personen in de lift. Op hoeveel manieren kunnen ze uitstappen? Dit is een 'talstelsel' probleem. Elke persoon kiest uit verdiepingen 1 t/m 8. Het antwoord moet dus zijn: 810 (En niet 108) Samenvatting We maken k keuzen uit N elementen. De vraag is nu: - mag een element 1 keer of meerdere keren worden gekozen - is de volgorde van kiezen wel of niet van belang Onderstaande tabel geeft tenslotte het aantal mogelijke keuzes voor elk geval. k keuzen uit N elementen volgorde van kiezen wel van belang niet van belang talstelsel dierentuin element meerdere malen kiezen Nk ( N - 1 + k N - 1 ) bestuur corveeploeg element 1 maal kiezen N! (N - k)! ( N k )