Arrange 6 adults and 12 children in 5 rooms, with at least 1 adult in each room

Question

Problem: How many ways can you arrange 6 adults and 12 children in 5 rooms of max 4 people such that there is at least 1 adult per room. Every person and room is distinguishable.

My take from the problem is the following:

1. There are 2 distinct ways to place 18 people in room of 4: $\{4, 4, 4, 4, 2\}$ and $\{4,4,4,3,3\}$
2. For the first sequence, I can start by fixing all the adults in every room in the following manner: $\binom{6}{2} \times \binom{4}{1} \times \binom{3}{1} \times \binom{2}{1} \times \binom{1}{1}$

3. Now there are 2 cases:

   1. The room with 2 adults is the one with 2 people $\binom{12}{0} \times \binom{12}{3} \times \binom{9}{3} \times \binom{6}{3} \times \binom{3}{3}$
   2. The room where 2 adults is among one that contains 4 people $\binom{12}{2} \times \binom{10}{3} \times \binom{7}{3} \times \binom{4}{3} \times \binom{1}{1}$

4. There are $5!$ ways to shuffle the rooms around since they are distinguishable

Adding the 2 cases in (3) and multiplying it with (2) and (4) should in my opinion give me the answer with the sequence $\{4, 4, 4, 4, 2\}$. Is there anything wrong with my reasoning?

Answer 1

Just for fun let's look at how we might solve this with generating functions.

Firstly, a room must have at most $2$ adults due to the pigeonhole principle. If it has $1$ adult then it can have $0,1,2$ or $3$ children, and if it has $2$ adults then it can have $0,1$ or $2$ children due to restricted capacity of $4$ people. We can express these possibilities for each room with the finite $2$-variable exponential series

$$x\left(1+y+\frac{1}{2!}y^2+\frac{1}{3!}y^3\right)+\frac{1}{2!}x^2\left(1+y+\frac{1}{2!}y^2\right)$$

$x$ is the enumerator for the number of adults and $y$ is the enumerator for number of children.

There are $5$ rooms, so to combine all possibilities for the rooms we must raise this to the power $5$:

$$\left(x\left(1+y+\frac{1}{2!}y^2+\frac{1}{3!}y^3\right)+\frac{1}{2!}x^2\left(1+y+\frac{1}{2!}y^2\right)\right)^5$$

and we want, as our answer, the coefficient of $x^6y^{12}/(6!12!)$ in this double exponential generating function.

Well, that can be done manually by considering cases (hint: there are only $4$) but I will use the online free open source computer algebra system "sage" with the following input:

y=var('y')
show(factorial(6)*factorial(12)*expand((x*(1+y+y^2/2+y^3/6)+x^2/2*(1+y+y^2/2))^5).coefficient(x^6).coefficient(y^12))

and sage outputs (in MathJax format):

$$34\,594\,560\,000\tag{Answer}$$

Does that agree with your answer? If not, please double check as I have done so with this one.

---

Okay, so if you are not acquainted with generating functions here is how to count the $4$ cases manually:

The $4$ types of room filling are:

$$\begin{array}{cccccc}\text{type 1}&(2,0) & (1,3) & (1,3) & (1,3) & (1,3)\\ \text{type 2}&(2,1) & (1,2) & (1,3) & (1,3) & (1,3)\\ \text{type 3}&(2,2) & (1,1) & (1,3) & (1,3) & (1,3)\\ \text{type 4}&(2,2) & (1,2) & (1,2) & (1,3) & (1,3)\\\end{array}$$

where $(\text{adults},\text{children})$ tells us how a room is to be filled with adults and children.

We can count each type by first choosing the room with $2$ adults in $\binom{5}{1}$ ways then distributing adults to rooms in $\frac{6!}{2!1!^4}$ ways. Then, for each type we distribute children to the rooms using a similar logic to the adult fillings:

$$\begin{align}\text{type 1}&=\binom{5}{1}\frac{6!}{2!1!^4}\frac{12!}{3!^4}\\[1ex] \text{type 2}&=\binom{5}{1}\frac{6!}{2!1!^4}\binom{4}{1}\frac{12!}{1!2!3!^3}\\[1ex] \text{type 3}&=\binom{5}{1}\frac{6!}{2!1!^4}\binom{4}{1}\frac{12!}{2!1!3!^3}\\[1ex] \text{type 4}&=\binom{5}{1}\frac{6!}{2!1!^4}\binom{4}{2}\frac{12!}{2!^33!^2}\end{align}$$

giving:

$$\begin{align}\text{type 1}&=665\,280\,000\\ \text{type 2}&=7\,983\,360\,000\\ \text{type 3}&=7\,983\,360\,000\\ \text{type 4}&=17\,962\,560\,000\\ \text{total}&=34\,594\,560\,000\tag{Answer}\end{align}$$

Answer 2

You could drive your consideration under 1. even further: you would have the following patterns (using a = adult, c = child):
$A = \{aacc, accc, accc, accc, ac\}$,
$B = \{accc, accc, accc, accc, aa\}$,
$C = \{aacc, accc, accc, acc, acc\}$,
$D = \{accc, accc, accc, aac, acc\}$.

Now let us consider first the rooms to be undistinguishable. Thus the filling pattern can be considered fixed in the above order. Then we get groupings:
$gA = (\binom{6}{2}\cdot\binom{12}{2})\times(\binom{6-2}{1}\cdot\binom{12-2}{3})\times(\binom{6-3}{1}\cdot\binom{12-5}{3})\times(\binom{6-4}{1}\cdot\binom{12-8}{3})\times(\binom{6-5}{1}\cdot\binom{12-11}{1})$,
$gB = (\binom{6}{1}\cdot\binom{12}{3})\times(\binom{6-1}{1}\cdot\binom{12-3}{3})\times(\binom{6-2}{1}\cdot\binom{12-6}{3})\times(\binom{6-3}{1}\cdot\binom{12-9}{3})\times(\binom{6-4}{2}\cdot\binom{12-12}{0})$,
$gC = (\binom{6}{2}\cdot\binom{12}{2})\times(\binom{6-2}{1}\cdot\binom{12-2}{3})\times(\binom{6-3}{1}\cdot\binom{12-5}{3})\times(\binom{6-4}{1}\cdot\binom{12-8}{2})\times(\binom{6-5}{1}\cdot\binom{12-10}{2})$,
$gD = (\binom{6}{1}\cdot\binom{12}{3})\times(\binom{6-1}{1}\cdot\binom{12-3}{3})\times(\binom{6-2}{1}\cdot\binom{12-6}{3})\times(\binom{6-3}{2}\cdot\binom{12-9}{1})\times(\binom{6-5}{1}\cdot\binom{12-10}{2})$.

Finally you can mix up the room numbers as well, thus you get the sequence counts:
$sA = \frac{5!}{1! \cdot 3! \cdot 1!}$,
$sB = \frac{5!}{4! \cdot 1!}$,
$sC = \frac{5!}{1! \cdot 2! \cdot 2!}$,
$sD = \frac{5!}{3! \cdot 1! \cdot 1!}$.

Thus you get as individual possibilities:
$pA = gA \cdot sA$,
$pB = gB \cdot sB$,
$pC = gC \cdot sC$,
$pD = gD \cdot sD$.

Or finally as total possibility count:
$P = pA + pB + pC + pD$.

(The actual calculation is kept for you.)

---rk