Stel er is een blind date met 2 mannen en 3 vrouwen. Elke man mag één vrouw van zijn voorkeur opgeven en tegelijkertijd mag elke vrouw één man van haar voorkeur opgeven. Er is een match als een man en een vrouw elkaar kiezen: man A kiest vrouw B en vrouw B kiest man A.

Het aantal matches dat tot stand kan komen, is nul, één of twee. Als we bij alle combinaties in een spreadsheet uitwerken, dan komen we op 72 mogelijke combinaties (32 × 23 = 72), waarbij er 12 keer twee matches zijn, 48 keer één match en 12 keer geen match.

‘Het is ondoenlijk om dit in een spreadsheet uit te rekenen voor 3 mannen en 4 vrouwen’, schreef iemand op de WisFaq, een digitale wiskundevraagbaak voor middelbare scholieren. De persoon in kwestie vroeg zich af of er een algemene formule voor bestaat (zie http://http://tinyurl.com/q9p2pk6).

Inclusie-exclusie

Als we $a$ mannen en $b$ vrouwen hebben, dan is het aantal mogelijke uitkomsten gelijk aan $a + 1$ als $a ≤ b$, en $b + 1$ als $b ≤ a$. (Bij 2 mannen en 3 vrouwen hebben we 2 + 1 = 3 mogelijke uitkomsten: 0 keer een match, 1 keer een match of 2 keer een match.)

Het aantal mogelijke combinaties is $b^a × a^b$. Wat is vervolgens de formule om uit te rekenen hoe vaak een bepaald aantal matches voorkomt? (Bij 2 mannen en 3 vrouwen zijn er drie mogelijke uitkomsten op 72 mogelijke combinaties, waarbij de drie mogelijke uitkomsten respectievelijk 12, 48 en 12 keer voorkomen.)

In het blind date-probleem kiest elke man één vrouw en elke vrouw één man, bijvoorbeeld door de naam op een briefje te schrijven. In het geval $a = 2$ en $b = 3$ had de vraagsteller zelf uitgerekend dat je de briefjes op 72 manieren kunt invullen, waarbij 12 keer nul matches optreden, 48 keer één match en 12 keer twee matches. Dit had hij uitgerekend door alles in een spreadsheet uit te werken. Bij $a = 3$ en $b = 4$ had hij de moed opgegeven, omdat het ondoenlijk leek.

Er is een telmethode die hier soelaas kan brengen, namelijk het principe van inclusie-exclusie. Dat principe hebben we al eerder in dit blad aan het werk gezien en ook nu zal het ons weer goede diensten bewijzen.

Twee mannen en drie vrouwen

We doen eerst het concrete geval met $a = 2$ en $b = 3$. Het totaal aantal manieren om briefjes met voorkeuren in te vullen is $3^2 × 2^3$: iedere man kan drie namen invullen en iedere vrouw kan twee namen invullen, en dat onafhankelijk van elkaar. Dit is ons eerste getal: 72 manieren om de briefjes in te vullen.

Vervolgens kijken we naar één stel, zeg Victor– Ludmila, zie de illustratie op de vorige pagina’s. Het aantal manieren om de briefjes in te vullen zó dat dit paar gevormd wordt, is $3^{2–1} × 2^{3–1} = 12$: Walter, de andere man, heeft de keuze uit drie namen, en Mary en Nina, de andere twee vrouwen, hebben elk de keuze uit twee namen.

We kunnen 6 stelletjes maken, dus het lijkt of er 6 × 12 = 72 manieren zijn om ten minste één stel te vormen. We hebben echter de mogelijkheden met twee stellen dubbel geteld. We onthouden het getal 72 en gaan kijken hoeveel dubbeltellingen we eraf moeten trekken.
Bekijk nu eens twee stelletjes: Victor–Ludmila en Walter–Nina. Om deze stellen te maken, kan de derde vrouw twee namen invullen. Dus voor elk tweetal stelletjes zijn er twee manieren om die tot stand te brengen.

Hoeveel tweetallen stelletjes zijn er? Dat zijn er zes: neem twee vrouwen (drie manieren) en wijs ze elk een man toe (twee manieren). Nu volgt dat er precies 6 × 2 manieren zijn om de briefjes zó in te vullen, dat er twee stellen ontstaan. De reden is dat als we voor elk tweetal stellen de twee manieren nemen en die bij elkaar voegen, we niets dubbel tellen. Ga maar na: een invulmogelijkheid die Victor– Ludmila en Walter–Nina oplevert, kan niet ook Victor–Ludmila en Walter–Mary opleveren. Dit is ons tweede getal: 6 × 2 = 12 manieren om twee stellen te vormen.

Het aantal mogelijkheden met ten minste één match is 72 – 12 = 60 (ons eerste getal minus ons tweede getal). Er zijn dus 12 manieren waarbij geen enkel stel gevormd wordt. Verder is het aantal mogelijkheden om precies één stel te vormen gelijk aan 72 – (12 + 12) = 48.

A mannen en B vrouwen

Hoe zit het nu algemeen? Net als hierboven nemen we een aantal stelletjes en kijken op hoeveel manieren de briefjes ingevuld kunnen worden om die stelletjes (en misschien nog meer) te vormen. Maar eerst, het totaal aantal manieren om de briefjes in te vullen is $b^a × a^b$: iedere man heeft $b$ keuzen, iedere vrouw heeft er $a$, en iedereen kiest onafhankelijk van elkaar.

Bij één voorgegeven stel zijn er $b^{a–1} × a^{b–1}$ mogelijkheden: de ‘andere’ mannen en vrouwen kunnen nog vrij kiezen. Omdat er $a × b$ stellen voorgegeven kunnen worden krijgen we, als we al deze mogelijkheden optellen, $(a × b) × (b^{a–1} × a^{b–1})$ mogelijkheden om ten minste één stel te vormen, maar daar zitten net als eerder dubbeltellingen tussen.

We moeten dus iets aftrekken; we kijken daarom naar het aantal mogelijkheden dat twee voorgegeven stellen oplevert. Dat is niet moeilijk: $b^{a–2} × a^{b–2}$: de rest van de mannen en vrouwen hebben nog vrije keuze. Als we twee stellen willen vastleggen, gaat dat als volgt. Kies twee mannen, kies twee vrouwen, en koppel ze. Dat levert
$${a \choose 2} × {b\choose 2}×2$$
tweetallen paren op. Al die mogelijkheden bij elkaar opgeteld levert
$${a \choose 2} × {b\choose 2}×2×b^{a−2} ×a^{b−2}$$
mogelijkheden op, weer met dubbeltelling, nu van mogelijkheden die drie of meer stellen opleveren. In het geval $a = 2$ hadden we daar geen last van, maar in het algemeen moeten we hier natuurlijk rekening mee houden.

We gaan verder: neem $k ≤ a$ en neem $k$ voorgegeven stellen. Daar horen, net als boven, $b^{a–k} × a^{b–k}$ invulmogelijkheden bij. Zo’n voorgegeven $k$-tal maken gaat net als bij twee stellen: $k$ mannen kiezen, $k$ vrouwen kiezen, en koppelen, in totaal dus
$${a \choose k} × {b\choose k}×k!$$

mogelijke $k$-tallen paren. Als we al die aantallen mogelijkheden bij elkaar optellen, krijgen we dus

$$T_k = {a \choose k} × {b\choose k}\times k! \times b^{a−k} \times a^{b−k}$$

Uit deze formule volgt overigens ook dat $T_1 = b^a \times a^b$, dus T1 is gelijk aan het totaal aantal mogelijkheden.

Het principe van inclusie-exclusie zegt nu hoe we het aantal keuzemogelijkheden met nul paren kunnen tellen. Neem het totale aantal $b^a \times a^b$ en trek daar $T_1$ van af, tel $T_2$ daar bij op, trek $T_3$ af, tel $T_4$ op, enzovoorts. In formulevorm ziet dat er zo uit:

$$b^a \times a^b + \sum_{k=1}^a (−1)^k T_k .$$

Verder is $T_a$ het exacte aantal invulmogelijkheden die precies $a$ paren opleveren: net als bij $a = 2$ wordt bij het opschrijven van $T_a$ niets dubbel geteld.

Drie mannen en vier vrouwen

Even terug naar de vraag uit de Wisfaq. We kunnen de getallen $T_1, T_2$ en $T_3$ snel uitrekenen:

• $T_1 = 4^3 \times 3^4 = 64 \times 81 = 5184,$
• $T_2 ={3 \choose 2}\times {4 \choose 2}\times 2 \times 4^1 \times 3^2 = 1296,$
• $T_3 ={3 \choose 3} {4 \choose 3} \times 3! \times 40 \times 31 = 72.$

Dus, nul stelletjes vinden we bij $$5184 – 5184 + 1296 – 72 = 1224$$

invulmogelijkheden. En bij 72 mogelijkheden vinden we drie stelletjes.

Hoe zit het nu met de rest? Hoe vaak vinden we precies één stel en hoe vaak precies twee stellen?

Nog meer rekenwerk

Met het principe van inclusie-exclusie kun je ook bepalen hoe vaak er precies één stel gevormd wordt. We leggen één stel vast en tellen, voor elke $k ≤ a – 1$, het aantal voorkeursuitspraken die (ten minste) $k$ extra matches opleveren. We krijgen, als boven:

$$S_k = {a-1 \choose k}\times {b-1 \choose k}\times k! \times b^{a-k-1} \times a^{b-k-1}.$$

Immers, we voeren achtereenvolgens uit: $k$ mannen kiezen, $k$ vrouwen kiezen, $k$ matches maken en de rest willekeurig laten kiezen. Met inclusie-exclusie halen we de dubbeltellingen weg: er zijn

$$b^{a−1} \times a^{b−1} + \sum_{k=1}^{a−1} (−1)^k S_k$$

mogelijkheden met alléén onze gegeven match. Vermenigvuldig dit met $a \times b$ om het totaal aantal keuzen dat één stel oplevert te krijgen (merk op dat we hier niets dubbel tellen!).

Nu kunnen we nog $a = 3$ en $b = 4$ invullen, eerst bij één stel:

• totaal: $42 \times 33 = 432,$
• $S_1 = 216,$
• $S_2 = 18.$

Inclusie-exclusie: 432 – 216 + 18 = 234 per uniek stel. En dus $12 \times 234 = 2808$ keuzemogelijkheden met één stel. Blijft over 5184 – (2808 + 72) = 2304 mogelijkheden met precies twee stellen.

Opdracht. Op soortgelijke manier is het nu mogelijk om formules te maken voor het aantal mogelijkheden met precies twee, precies drie, ... stelletjes.

Hoeveel mogelijkheden om op twee matches uit te komen krijg je voor de situatie met vijf mannen en vier vrouwen?

(Het antwoord is $120 \times 1144 = 137.280.$)