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 / vrouw B kiest man A). Mogelijke uitkomsten per keuzemoment: geen match, 1 match of 2 matches.
Als ik bij 2 mannen en 3 vrouwen alle combinaties in een spreadsheet uitwerk, dan kom ik op 72 mogelijke combinaties (= 2 tot de 3e macht x 3 kwadraat = 8 x 9 = 72), waarbij er 12 keer 2 matches zijn, 48 keer 1 match en 12 keer geen match.
Ditzelfde in een spreadsheet uitrekenen voor 4 mannen en 3 vrouwen is ondoenlijk. Daar moet een algemene formule voor zijn.
Als ik a mannen heb en b vrouwen, dan is het aantal mogelijke matches:
a+1, als a $<$ b
b+1 als b $<$ a
(2 mannen en 3 vrouwen geeft 2+1=3 mogelijke uitkomsten: 0x, 1x of 2x een match).
Het aantal mogelijke combinaties is a tot de macht b x b tot de macht a.
Wat is vervolgens de formule om uit te rekenen hoe vaak elk van de mogelijke 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).
Harm Weistra
18-5-2015
Hier een paar opmerkingen die je wat verder kunnen helpen.
Stel je hebt een matching waar $k$ stellen zijn gevormd. Zo'n matching kan dan horen bij het volgende aantal voorkeursuitspraken:
$$
b^{a-k}\times a^{b-k}
$$NB: dit wil niet zeggen dat onze matching de maximale is die bij die voorkeuren hoort; alleen dat hij er bij past.
Voorts zijn er
$$
{a \choose k}\times{b\choose k}\times k!
$$matchings met $k$ stelletjes: kies $k$ mannen, $k$ vrouwen en een bijectie tussen de verzamelingen.
Nu kun je voor twee uitkomsten een formule opstellen (we nemen aan dat $a\le b$).
1) het aantal voorkeuren dat een matching met $a$ stelletjes oplevert: vul $k=a$ in
$$
{b\choose a}\times a!\times a^{b-a}
$$2) het aantal voorkeuren die geen enkele matchings opleveren:
voor een paar $(m,v)$ noteren we met $A(m,v)$ de verzameling van paren functies $f$ en $g$ (voorkeursuitspraken) die $m$ en $v$ koppelen, dus $f(m)=v$ en $g(v)=m$. Uit wat hierboven staat, $k=1$, volgt dat $A(m,v)$ altijd $b^{a-1}\times a^{b-1}$ elementen heeft.
Verder: als $m_1$ ongelijk is aan $m_2$ dan is $A(m_1,v)\cap A(m_2,v)$ leeg (er is geen functie $g$ met $g(v)=m_1$ en $g(v)=m_2$), evenzo geldt $A(m,v_1)\cap A(m,v_2)=\emptyset$ als $v_1$ niet gelijk is aan $v_2$. Conclusie: als we $k$ verschillende paren $(m_1,v_1)$, ..., $(m_k,v_k)$ hebben met $\bigcap_{i=1}^kA(m_i,v_i)$ niet leeg dan vormen die paren een matching en heeft die doorsnede $b^{a-k}\times a^{b-k}$ elementen. Kijk nu naar de formule in onderstaande link (Principe van Inclusie-Exclusie) het aantal voorkeursuitspraken dat ten minste één stelletje oplevert is gelijk aan
$$
\sum_{k=1}^a (-1)^{k-1}{a \choose k}\times{b\choose k}\times k!\times b^{a-k}\times a^{b-k}
$$Het aantal voorkeuren zonder ook maar één matching is dus
$$
b^a\times a^b-\sum_{k=1}^a (-1)^{k-1}{a \choose k}\times{b\choose k}\times k! \times b^{a-k}\times a^{b-k}
$$De term bij $k=1$ is in dit geval gelijk aan het totaal (schrijf maar uit) dus dit is gelijk aan
$$
\sum_{k=2}^a (-1)^{k}{a \choose k}\times{b\choose k}\times k!\times b^{a-k}\times a^{b-k}
$$In het geval $a=2$ en $b=3$ kom je hiermee op de getallen die je al had. Als $a=3$ en $b=4$ dan hebben we de volgende getallen: totaal aantal $4^3\times 3^4$, de afzonderlijke termen: $4^3\times3^4$ ($k=1$), $4^2\times3^4$ ($k=2$), en $2^3\times3^2$ ($k=3$). Dus $72$ voorkeuren met $3$ matches en $4^2\times3^4 - 2^3\times 3^2=1224$ met $0$ matches.
Toevoeging (1-6-2015): de andere aantallen zijn op dezelfde wijze als hierboven te bepalen; als voorbeeld het aantal voorkeuren met precies één match.
Leg één match vast; nu tellen we, voor elke $k\le a-1$, het aantal voorkeursuitspraken die (ten minste) $k$ extra matches opleveren. We krijgen, als boven:
$$
{a-1\choose k}\times{b-1\choose k}\times k!\times b^{a-k-1}\times a^{b-k-1}
$$($k$ mannen kiezen, $k$ vrouwen kiezen, $k$ matches maken en de rest willekeurig laten kiezen).
Met inclusie-exclusie komen we nu op
$$
b^{a-1}\times a^{b-1}-\sum_{k=1}^{a-1} (-1)^{k-1} {a-1\choose k}\times{b-1\choose k}\times k!\times b^{a-k-1}\times a^{b-k-1}
$$mogelijkheden met alléén onze gegeven match.
Vermenigvuldig dit met $a\times b$ om het totaal aantal keuzen met één match te krijgen.
In het geval $a=3$ en $b=4$ kom ik op $5184$ mogelijkheden totaal, waarvan $1224$ met $0$ matches, $2808$ met één match, $1080$ met twee matches en $72$ met drie.Zie Principe van inclusie-exclusie [http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle]
kphart
31-5-2015
#75609 - Formules - Ouder