WisFaq!

Twintig personen verdelen over 4 groepen

Op hoeveel manieren kan je een groep van 20 personen indelen in 4 deelgroepen, waarbij er in elke deelgroep minstens 1 persoon zit. Elke deelgroep heeft een aparte taak te vervullen.

Sam Gobbaerts
19-1-2009

Antwoord

Wat je in feite moet tellen zijn de functies van {1,2,...,20} naar {1,2,3,4} die alle waarden aannemen. Dat gaat het snelst door naar het complement te kijken: voor i=1,2,3,4 schrijf je A_i={f:i zit niet in het beeld van f}; dus A₁ bestaat uit de functies die van {1,2,...,20} naar {2,3,4} gaan en dat zijn er 3²⁰. Het complement van onze gezochte verzameling is dan de vereniging van de vier A_i. Het principe van inclusie-exclusie (zie de link hieronder voor de formule) impliceert dat het aantal elementen van die vereniging gelijk is aan 4·3²⁰-6·2²⁰+4·1²⁰. Het gevraagde antwoord is dan dit getal afgetrokken van het totaal aantal functies, dus 4²⁰-(4·3²⁰-6·2²⁰+4·1²⁰).

Zie Wikipedia: Inclusion-exclusion principle [http://en.wikipedia.org/wiki/Inclusion-exclusion_principle]

kphart
21-1-2009