# Probabilities and Stirling numbers of the second kind

I would like to solve the following problem, from the book Understanding Probability by Henk Tijms.

Fifteen tourists are stranded in a city with four hotels, all of which are located near each other in the city center. Each hotel has enough rooms available to accomodate all 15 tourists. Each tourist randomly chooses a hotel, independently of the choices made by the others. What is the probability that not all four hotels will be chosen?

My idea is as follows. Denote by $A, B, C, D$ the four hotels, and by $P(A\cap B\cap C\cap D)$ the probability that all four hotels are chosen by at least one tourist. I would start by computing $P(A\cap B\cap C\cap D)$, and then take the complementary probability.

Here is where I am stuck. A possible approach would be that of writing down a table such as:

$$\begin{array}{ccccc} A & B & C & D & \text{probability} & \text{count} \\ \hline 1 & 1 & 1 & 12 & \binom{15}{1}\binom{14}{1}\binom{13}{1}/4^{15} & 4 \\ 1 & 1 & 2 & 11 & \binom{15}{1}\binom{14}{1}\binom{13}{2}/4^{15} & 4 \\ \dots \end{array}$$ However, this approach is clearly too time-demanding (and error-prone) in this case, so I guess that the solution should be related to the number of ways to partition a set of fifteen elements in four nonempty subsets, counted by the probability of each of these subsets. I do not know how to develop this further.

Use exponential generating functions to compute the probability that all four hotels will be chosen (some person in each hotel). We first compute the assignments of people to hotels that are surjective. Note that $$(e^x-1)^4 =\left(x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dotsb\right)^4 =\sum_{n=0}^\infty \left( \sum_{k_1+\dotsb+k_4=n;\,k_i\geq1}\frac{n!}{k_1!k_2!k_3!k_4!} \right)\frac{x^n}{n!}\tag{1}$$ We want the coefficient of $x^{15}/15!$ (think of words of length $15$ over the alphabet of letters (in this case hotels) $H_1,H_2,H_3,H_4$ in which each letter appears at least once). But then note that $$(e^x-1)^4=e^{4x}-4e^{3x}+6e^{2x}-4e^{x}+1.\tag{2}$$ Hence the coefficient of $x^{15}/15!$ and thus the number of assignments of people to hotels in which each each hotel is chosen at least once is $$4^{15}-4\cdot3^{15}+6\cdot2^{15}-4\tag{3}$$ and hence the probability that not all four hotels will be chosen is $$1-\frac{4^{15}-4\cdot3^{15}+6\cdot2^{15}-4}{4^{15}}.$$ The same result can be obtained by inclusion-exclusion.
As a side note the number of surjective functions from people to hotels is counted by the ordered stirling numbers of the second kind. In this case it is $4!\times S(15,4)$. Hence the probability that not all four hotels will be chosen may also be written as $$1-\frac{4!\times S(15,4)}{4^{15}}.$$
• Thanks. I understand that $S(15,4)/4^{15}$ is the fraction of sequences of length 15 containing all the four letters $A,B,C,D$, but why the $4!$? I suppose this is related to the number of permutations of four elements, corresponding to the column "count" in the table I wrote in my original post. – J. D. Jan 3 '18 at 8:52
$P(A)=\binom{4}{3}(0.75)^{15}-\binom{4}{2}(0.5)^{15}+\binom{4}{1}(0.25)^{15} \approx 0.053$
where $A$- not all four hotels will be chosen.