De redactie kreeg een vraag van Pythagoras-lezer Henk van Hulsel over iemand die met een lift naar de zevende verdieping van een gebouw met tien verdiepingen moest. Er stonden nog vijf andere mensen te wachten en onze lezer wilde weten op hoeveel manieren de lift onderweg $0, 1, 2, 3, 4,$ of $5$ keer kon stoppen. Voor alle duidelijkheid: Henk ging ervan uit dat er onderweg niemand instapte, en dus dat er alleen gestopt werd om iemand uit te laten stappen.

Henk kreeg de telling niet kloppend en vroeg ons om advies. Hij had ervoor gekozen alle mogelijke verdelingen van die andere vijf mensen over de verdiepingen mee te nemen. Daar kun je al een vraag bij stellen: waarom zou je rekening houden met wat er gebeurt als je de lift al uit bent? Over de verschillende interpretaties van de vraag zullen we het aan het eind nog hebben. We rekenen eerst maar eens met onze lezer mee.

Vijf verschillende personen over tien verschillende verdiepingen verdelen gaat op $10^5$ manieren: iedereen kiest onafhankelijk van elkaar een verdieping. Henk telde allerlei manieren om sommige (ook nul) van de vijf personen over verdiepingen $1$ tot en met $6$ te verdelen en kwam via een uitgebreide tabellering tot $81\,155$. En dus vroeg hij zich af: waar waren de andere $18\,845$ manieren gebleven?

Die andere manieren waren niet geteld. Hoe dat kwam kunnen we aan een regel uit de tabel zien. Die regel telde het aantal manieren om twee keer te stoppen om drie van de vijf anderen uit te laten stappen (de andere twee gingen mee tot $7$ of hoger). De regel luidde:

$\color{orange}{2\ naar\ A,\ 1\ naar\ B,\ 2\ naar\ 7\ tot\ en\ met\ 10.}$

Hierbij waren $A$ en $B$ de twee verdiepingen waar die drie uitstappen.

Wat was het probleem? De $A$ en $B$ waren vast genomen, zeg $A$ lager dan $B$. Maar dan worden de mogelijkheden waar er één persoon op $A$ uitstapt en twee op $B$ dus niet meegeteld. Het getal op deze regel moest dus met $2$ worden vermenigvuldigd. Het gevonden aantal $7\,200$ moest verdubbeld worden tot $14\,400$. Alle aantallen op regels waar ongelijke aantallen op verschillende verdiepingen uitstapten moesten aangepast worden.

Hoe dan wel?

In plaats van de telling te repareren, is het handig iets anders te werk te gaan. We voeren even twee letters in: $n$ en $k$. Hierbij staat $n$ voor het aantal mensen dat vóór de zevende verdieping uitstapt en $k$ staat voor het aantal keren dat de lift stopt. Natuurlijk geldt altijd $k \le n$. In onze situatie kunnen $n$ en $k$ alle waarden van $0$ tot en met $5$ aannemen, mits inderdaad $k \le n$, met één uitzondering.

Als de lift nooit stopt stapt er niemand uit, dus als $k = 0$ dan geldt ook $n = 0$, en in dat geval stappen alle vijf personen uit op verdiepingen $7$ tot en met $10$ en dat levert $4^5 = 1024$ verdelingen op.

Als $k \ge 1$ dan kan $n$ van $k$ tot en met $5$ lopen. Op hoeveel manieren kan de lift in een dergelijk geval stoppen? We kiezen $k$ verdiepingen en $n$ personen. Dat gaat op respectievelijk $\left(\begin{matrix}6\\k\end{matrix}\right)$ en $\left(\begin{matrix}5\\n\end{matrix}\right)$ manieren; die twee factoren krijgen we dus al. Verder verdelen de overige $5 - n$ personen zich over verdiepingen $7$ tot en met $10$, dus dat geeft een factor $4^{5-n}$.

Wat overblijft is de $n$ personen over de $k$ verdiepingen verdelen en wel zó dat elk van de $k$ verdiepingen ten minste één persoon krijgt. Dan moeten we twee dingen doen: de $n$ personen in $k$ niet-lege groepjes verdelen en dan elk van die groepen aan een verdieping toewijzen. Dat laatste kan op $k!$ manieren want dat zijn gewoon alle mogelijke rangschikkingen van de $k$ groepen. Nu nog het verdelen in $k$ groepjes. Onze getallen zijn maar klein, en met wat volharding kun je voor alle paren die we tegen kunnen komen die aantallen wel bepalen.

Maar we willen natuurlijk een formule hebben! De getallen die we zoeken zijn heel bekend en heten Stirlinggetallen van de tweede soort en ze worden vaak geschreven als $S(n,k)$, of ook als $\left\{\begin{matrix}n\\k\end{matrix}\right\}$ (net als binomiaalcoëfficiënten maar dan met $\{\}$ in plaats van $()$ eromheen).

Bij gegeven $n$ en $k$ krijgen we dus het volgende antwoord:

$$\left(\begin{matrix}6\\k\end{matrix}\right) \cdot \left(\begin{matrix}5\\n\end{matrix}\right) \cdot \left\{\begin{matrix}n\\k\end{matrix}\right\}\cdot k!.$$

Dit moeten we nog met $4^{5-n}$ vermenigvuldigen omdat we ook tellen hoe de anderen zich over de bovenste vier verdiepingen verdelen, dus

$$\left(\begin{matrix}6\\k\end{matrix}\right) \cdot \left(\begin{matrix}5\\n\end{matrix}\right) \cdot \left\{\begin{matrix}n\\k\end{matrix}\right\} \cdot k! \cdot 4^{5-n}.$$

En bij gegeven $k$ groter dan $0$ krijgen we

$$\sum_{n=k}^5\left(\begin{matrix}6\\k\end{matrix}\right)\cdot\left(\begin{matrix}5\\n\end{matrix}\right)\cdot\left\{\begin{matrix}n\\k\end{matrix}\right\}\cdot k!\cdot 4^{5-n}$$

manieren waarop de lift op $k$ verdiepingen kan stoppen. We moeten dus alleen nog een manier vinden om die Stirlinggetallen snel uit te rekenen.

Sommige Stirlinggetallen zijn makkelijk te bepalen: als $n \ge 1$ dan

$\displaystyle{\left\{\begin{matrix}n\\0\end{matrix}\right\}}=0$ en $\displaystyle{\left\{\begin{matrix}n\\1\end{matrix}\right\} = \left\{\begin{matrix}n\\n\end{matrix}\right\}} = 1$.

In nul groepen verdelen kan niet en je kunt $n$ personen maar op één manier in één groep verdelen (iedereen bij elkaar) of in $n$ groepen (iedereen alleen).

Het mooie is dat je $\left\{\begin{matrix}n\\k\end{matrix}\right\}$ in eerdere Stirlinggetallen kunt uitdrukken:

$$\left\{\begin{matrix}n\\k\end{matrix}\right\}=k\cdot\left\{\begin{matrix}n-1\\k\end{matrix}\right\}+\left\{\begin{matrix}n-1\\k-1\end{matrix}\right\}.$$

Er zijn immers twee soorten verdelingen:

• die waarbij getal $n$ alleen blijft; dan moeten de andere $n - 1$ in $k - 1$ groepen verdeeld worden, dat geeft $\left\{\begin{matrix}n-1\\k-1\end{matrix}\right\}$, en
• die waar getal $n$ niet alleen blijft, dus waarbij zijn groepje ook iemand van de andere $n - 1$ bevat; dat komt neer op de andere $n - 1$ in $k$ groepen verdelen, op $\left\{\begin{matrix}n-1\\k\end{matrix}\right\}$ manieren, en $n$ bij elk van die groepen een keer laten aanschuiven, dus $k\cdot\left\{\begin{matrix}n-1\\k\end{matrix}\right\}$ in totaal.

Nu kun je in onze beperkte situatie de benodigde Stirlinggetallen snel uitrekenen, beginnend met $\displaystyle{\left\{\begin{matrix}n\\1\end{matrix}\right\} = \left\{\begin{matrix}n\\n\end{matrix}\right\}} = 1$ voor $n = 1, 2, 3, 4,$ en $5$. We hoeven er nog maar zes te doen.

• $\left\{\begin{matrix}3\\2\end{matrix}\right\} = 2\cdot \left\{\begin{matrix}2\\2\end{matrix}\right\} + \left\{\begin{matrix}2\\1\end{matrix}\right\} = 2\cdot 1+1=3;$
• $\left\{\begin{matrix}4\\2\end{matrix}\right\} = 2\cdot \left\{\begin{matrix}3\\2\end{matrix}\right\} + \left\{\begin{matrix}3\\1\end{matrix}\right\} = 2\cdot 3+1=7;$
• $\left\{\begin{matrix}5\\2\end{matrix}\right\} = 2\cdot \left\{\begin{matrix}4\\2\end{matrix}\right\} + \left\{\begin{matrix}4\\1\end{matrix}\right\} = 2\cdot 7+1=15;$
• $\left\{\begin{matrix}4\\3\end{matrix}\right\} = 3\cdot \left\{\begin{matrix}3\\3\end{matrix}\right\} + \left\{\begin{matrix}3\\2\end{matrix}\right\} = 3\cdot 1+3=6;$
• $\left\{\begin{matrix}5\\3\end{matrix}\right\} = 3\cdot \left\{\begin{matrix}4\\3\end{matrix}\right\} + \left\{\begin{matrix}4\\2\end{matrix}\right\} = 3\cdot 6+7=25;$
• $\left\{\begin{matrix}5\\4\end{matrix}\right\} = 4\cdot \left\{\begin{matrix}4\\4\end{matrix}\right\} + \left\{\begin{matrix}4\\3\end{matrix}\right\} = 4\cdot 1+6=10;$

Voor de regel van de tabel die we aan het begin bekeken betekent dit

$$\left(\begin{matrix}6\\2\end{matrix}\right)\cdot\left(\begin{matrix}5\\3\end{matrix}\right)\cdot\left\{\begin{matrix}3\\2\end{matrix}\right\}\cdot 2!\cdot 4^2=14\,400$$

als antwoord; het gegeven getal was dus inderdaad half goed, het dubbele is correct.

De antwoorden

Met een rekenmachientje, of een programma als Maple, zijn de antwoorden snel gevonden. We krijgen het volgende tabelletje:

$k$	aantal
$0$	$1\,024$
$1$	$12\,606$
$2$	$38\,250$
$3$	$36\,600$
$4$	$10\,800$
$5$	$720$
Totaal	$100\,000$

Andere overwegingen

Zoals aan het begin opgemerkt kun je je afvragen of de factor $4^{5-n}$ in de antwoorden nodig is. Dat is van belang als je de kansen wilt bepalen dat de lift onderweg $0, \dots, 5$ keer stopt.

In het model van de lezer delen we onze tellingen door $100\,000$ en krijgen we achtereenvolgens $0{,}01024$, $0{,}12606$, $0{,}38250$, $0{,}36600$, $0{,}10800$ en $0{,}00720$ (dezelfde getallen als in de tabel, met de komma vijf plaatsen naar links).

Als je het gedrag van de personen die op de $7^e$ verdieping of hoger uitstappen negeert laten we de factor $4^{5-n}$ weg uit onze formules. Dat betekent dat we voor $k = 0$ maar één mogelijkheid hebben: niet stoppen vóór de $7^e$ verdieping. Voor $k \ge 1$ komt er dan 

$$\sum_{n=k}^5\left(\begin{matrix}6\\k\end{matrix}\right)\cdot\left(\begin{matrix}5\\n\end{matrix}\right)\cdot\left\{\begin{matrix}n\\k\end{matrix}\right\}\cdot k!$$

en dat levert de volgende aantallen $186, 2\,700, 7\,800, 5\,400, 720$.

Het totaal aantal (inclusief de $1$ bij $k = 0$) is dan $16\,807$. De kansen zien er dan wel anders uit:

$k$	aantal	kans
$0$	$1$	$0{,}000059499$
$1$	$186$	$0{,}011067$
$2$	$2\,700$	$0{,}16065$
$3$	$7\,800$	$0{,}46409$
$4$	$5\,400$	$0{,}32129$
$5$	$720$	$0{,}042839$
Totaal	$16\,807$

 De grote vraag is nu: welk van de twee klopt? Dat is vaak een lastige vraag omdat niet altijd duidelijk is wat wel en wat niet belangrijk is.

Opgave 1 Onderzoek welke van de twee kansverdelingen de correcte is, en zo nee wat dan wel de juiste is. Je kunt bijvoorbeeld met Python of een andere taal proberen het probleem te simuleren en op die manier een staafdiagram van de frequenties te maken. Je kunt ook nog eens goed over het probleem nadenken en proberen te achterhalen wat belangrijk is voor de kansverdeling.

Een echte formule ^[ooo] 

Het zal niet makkelijk zijn, maar wie mee durft te gaan voorbij de drie rondjes, kan een expliciete formule afleiden voor de Stirlinggetallen van de tweede soort.

We doen het met getallen in plaats van personen: $\left\{\begin{matrix}n\\k\end{matrix}\right\}$ is het aantal manieren waarop je $\{1, \dots , n\}$ in $k$ niet-lege verzamelingen kunt verdelen. Voor het gemak korten we $\{1, \dots , n\}$ af met $[n]$.

De telmethode is die van Inclusie-Exclusie, die is al eens eerder in Pythagoras 56-2 gebruikt in een artikel over het koppelen van mensen aan hun voorkeuren: Blind dates.

We bepalen de Stirlinggetallen indirect. Als we $[n]$ in $k$ niet-lege verzamelingen verdeeld hebben, kunnen we die verzamelingen nummeren en dan de getallen in groep $i$ allemaal het label $i$ geven. Dat komt neer op het maken van een functie $f$ van $[n]$ naar $[k]$ met de eis dat voor elk element $j$ van $[k]$ er minimaal één $i$ in $[n]$ is met $f(i) = j$. Zo'n functie heet surjectief.

Elke surjectieve functie bepaalt een verdeling van $[n]$ in $k$ niet-lege deelverzamelingen met een nummering. We kunnen elke verdeling op $k!$ manieren nummeren, dus het aantal surjectieve functies van $[n]$ naar $[k]$ is gelijk aan $k!\cdot \left\{\begin{matrix}n\\k\end{matrix}\right\}$.

We gaan het aantal surjectieve functies van $[n]$ naar $[k]$ dus tellen. En dat doen we door de niet-surjectieve functies te tellen en dat aantal van het totaal, dat is $k^n$, af te trekken. Als een functie $f$ niet surjectief is, is er een $j \in [k]$ zó dat $f(i) \neq j$ voor alle $i \in [n]$. Hoeveel functies zijn er met $f(i) \neq j$ voor alle $i$? Dat zijn gewoon alle functies van $[n]$ naar $[k]\,\backslash\,\{j\}$, en dat zijn er dus $(k - 1)^n$.

Nu voeren we wat notatie in: $A_j$ is de verzameling van alle functies van $[n]$ naar $[k]$ die voldoen aan $f(i) \neq j$ voor alle $i$.

We hebben gezien dat $A_j$ precies $(k - 1)^n$ elementen heeft. Wat we willen is de vereniging $A_1 \cup \dots \cup A_k$ tellen. Ietwat naïef tellen we hun aantallen op en krijgen $k \cdot (k - 1)^n$.

Als we dat doen tellen we dingen dubbel, als namelijk voor alle $i \in [n]$ geldt dat $f(i) \neq 1$ en $f \neq 2$ dan wordt $f$ twee keer geteld: als element van $A_1$ en van $A_2$.

Niet getreurd, dan trekken we de dubbeltellingen af. Voor elk tweetal $j_1$ en $j_2$ zijn er $(k - 2)^n$ functies die niet de waarden $j_1$ en $j_2$ aannemen en die vormen de doorsnede $A_{j_1} \cap A_{j_2}$ van $A_{j_1}$ en $A_{j_2}$. Er zijn $\left(\begin{matrix}k\\2\end{matrix}\right)$ van die paren en doorsneden, dus als we hun aantallen optellen en van ons eerste getal aftrekken komt er

$$\left(\begin{matrix}k\\1\end{matrix}\right)(k-1)^n-\left(\begin{matrix}k\\2\end{matrix}\right)(k-2)^n.$$

(We hebben gebruikt dat $k=\left(\begin{matrix}k\\1\end{matrix}\right)$ om de formule mooi uit te laten komen.)

Je voelt hem al aankomen: we missen nu weer iets. Neem een functie $f$ die de waarden $1, 2,$ en $3$ niet aanneemt. Die hebben we eerst drie keer geteld in $A_1, A_2$, en $A_3$ – en daarna drie keer weggegooid in $A_1 \cap A_2$, $A_1 \cap A_3$ en $A_2 \cap A_3$. OK, dan voegen we alle drie-bij-driedoorsneden weer toe, er zijn $\left(\begin{matrix}k\\3\end{matrix}\right)$ van die doorsneden en die hebben allemaal $(k - 3)^n$ elementen. We komen uit op

$$\left(\begin{matrix}k\\1\end{matrix}\right)(k-1)^n-\left(\begin{matrix}k\\2\end{matrix}\right)(k-2)^n+\left(\begin{matrix}k\\3\end{matrix}\right)(k-3)^n.$$

Als je even nadenkt zie je dat we nu weer de vier-bij-vierdoorsneden moeten aftrekken, vijf-bij-vijf optellen enzovoort, tot en met $k - 1$.

Opgave 2 Waarom niet tot en met $k$? Wat weet je van de totale doorsnede $A_1\cap \dots \cap A_k$?

Dat beurtelings optellen en aftrekken leidt tot de volgende som: 

$$\sum_{j=1}^{k-1}(-1)^{j-1}\left(\begin{matrix}k\\j\end{matrix}\right)(k-j)^n.$$

Je kunt om de uitdrukking mooier te maken de $k$-de term zonder gevaar toevoegen want $(k - k)^n=0$:

$$\sum_{j=1}^{k}(-1)^{j-1}\left(\begin{matrix}k\\j\end{matrix}\right)(k-j)^n.$$

Dit moeten we van $k^n$ aftrekken, het antwoord is dus:

$$k!\cdot\left\{\begin{matrix}n\\k\end{matrix}\right\}=k^n-\sum_{j=1}^{k}(-1)^{j-1}\left(\begin{matrix}k\\j\end{matrix}\right)(k-j)^n.$$

Dat minteken kunnen we binnen de som halen door $(-1)^j$ te schrijven en omdat $\left(\begin{matrix}k\\0\end{matrix}\right)=1$ kunnen we de formule als volgt opschrijven:

$$\left\{\begin{matrix}n\\k\end{matrix}\right\}=\frac{1}{k!}\sum_{j=0}^k(-1)^j\left(\begin{matrix}k\\j\end{matrix}\right)(k-j)^n.$$

Pas de formule maar eens toe op de getallen die we bij het liftprobleem nodig hadden.