3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Your reasoning is correct. $\endgroup$ – N. F. Taussig Mar 23 '18 at 10:03
1
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ I haven't learned the generating function yet but it is quite interesting nonetheless. As for the manual method, it was quite different from my method but it seems to arrive at the same result. Just to be sure, in your method, the way of you distribute the children is by looking at the ways 3 children can fit in the room right? $\endgroup$ – Binyuan Sun Mar 23 '18 at 19:06
  • 1
    $\begingroup$ @BinyuanSun, yes. Specifically by looking at the ways up to 3 children can fit once the adults have already taken a room. It is encouraging that our answers are the same! With regards to generating functions, they sometimes help give an answer quicker (sadly not the case here) but at the very least they give a clear insight in to the structures we are trying to count and how to enumerate more systematically. See if you can see how the answer arises from the coefficient of $x^6y^{12}/(6!12!)$ in the expansion, you'll hopefully see that it gives the same 4 types as when counting manually. $\endgroup$ – N. Shales Mar 23 '18 at 20:13
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ May you explain the reason of the divisors in $sX$? $\endgroup$ – Binyuan Sun Mar 23 '18 at 15:34
  • $\begingroup$ (+1) I've only checked $pA$ but I reckon this answer checks out. Those terms $gA,gB,gC$ and $gD$ simplify significantly. $\endgroup$ – N. Shales Mar 23 '18 at 18:26
  • $\begingroup$ @BinyuanSun: There are 5 rooms to be swapped. One of them e.g. in $A$ is of type $aacc$ (unique) and one of them is of type $ac$ (unique too), but all other three all are of type $accc$, thus interchangeable. This gives $\frac{5!}[1! 3! 1!}$, as was mentioned. (The others are analogue.) $\endgroup$ – Dr. Richard Klitzing Mar 24 '18 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.