1
$\begingroup$

Question: $20$ distinct students are to be placed into four distinct dorms named: A, B, C, D. In how many ways can they be assigned to the four dorms, with the restriction that each dorm needs to have at least one student?

My attempt: The question says that each dorms must have at least one student. So, my first attempt is since there are four dorms, then the first dorm has $20$ choices to take in one of the $20$ students, and the second dorms then has $19$ choices to take in one students. The third dorms has 18 choices, and the fourth has $17$ choices. Now, each dorms has one student, and that leaves $16$ students left who may enter any one of the dorms, so the arrangement is $16^4$. So there are $20 \times 19 \times 18 \times 17 \times 16^4$ arrangements.

However, it seems that I can first distribute the 16 students into the dorms with $16^4$ arrangements, then distribute the remaining 4 students with $4!$ arrangements, so that each dorms has at least one student in them. So the total arrangement is $16^4 \times 4! < 20 \times 19 \times 18 \times 17 \times 16^4$. This don't seem right.

I appreciate it very much if anyone could help me out on this problem. Thank you.

$\endgroup$
4
  • $\begingroup$ Just to be clear. The rooms are distinguishable, and the students are distinguishable. Is that correct? Label the students 1,...,20. If students 1 and 2, swap dorms that changes the arrangement? And if all the students in dorm A move to dorm B and vice versa, that changes the arrangement? $\endgroup$ – almagest Jan 25 '20 at 20:15
  • $\begingroup$ @almagest yes, that's correct. All students and dorms are distinct. $\endgroup$ – TerminatorOfTerminators Jan 25 '20 at 20:25
  • 1
    $\begingroup$ Your method over counts badly. If, say, you had $5$ students in $A$ then you count that arrangement at least $5$ times (once for every student in $A$), and so on. $\endgroup$ – lulu Jan 25 '20 at 20:26
  • 1
    $\begingroup$ The usual method is to go by Inclusion Exclusion. That is, we start with $4^{20}$, which would be the answer if we allowed empty dorms. Now subtract the ways to do it with one specified empty dorm, namely, $4\times 3^{20}$, add back the ways with two specified empty dorms, and so on. $\endgroup$ – lulu Jan 25 '20 at 20:31
2
$\begingroup$

As has been remarked, your method probably should have led you to write $$20\times 19\times 17\times 16\times 4^{16}$$ but this is not correct. The problem is that, if multiple students are in a given norm, then there is no way to tell which one of them is the "special" one that you put in first, so you end up counting that arrangement once for every student in that dorm. Indeed, that answer is $>4^{20}$ which would be the correct answer if we allowed empty dorms, so the correct answer must be significantly smaller.

To illustrate the problem, suppose you had three students, $x,y,z$ in two dorms, $A,B$. Now the correct answer is clearly $6$. Why? Well, if you allowed empty dorms there would be $2^3=8$ as each student has two choices. We then exclude the two cases $((x,y,z), \emptyset)$ and $(\emptyset, (x,y,z))$. Indeed the list of solutions is just $$((x,y),z)\quad ((x,z), y)\quad ((y,z),x)\quad (x,(y,z))\quad (y,(x,z))\quad (z,(x,y))$$

but your method would give us $3\times 2\times 2^1=12$

The usual way to do is via Inclusion Exclusion. There would be $4^{20}$ ways if we allowed empty dorms. We first correct this by subtracting off the cases in which one specified dorm is empty, to get a correction of $$-\binom 41\times (4-1)^{20}$$ and then we add back those cases with two specified empty dorms, and finally subtract the cases with three specified empty dorms. Thus the answer is $$\sum_{i=0}^3(-1)^i\times \binom 4i\times (4-i)^{20}=1,085,570,781,624$$

$\endgroup$
0
2
$\begingroup$

You are looking for the number of surjections from a set with $20$ elements into a set with $4$ elements. By the Twelvefold way, that expression is $$4!\left\{{20\atop4}\right\}=1\ 085\ 570\ 781\ 624$$ where the expression in brackets is a Stirling number of the second kind.

$\endgroup$
1
$\begingroup$

There are $4^{20}$ to assign students to dorms if we allow dorms to be empty.

If at least one dorm is empty there are $3^{20}$ ways to assign students to the remaining 3 dorms. There are 4 dorms that could be the empty dorm. But we are over-counting the cases were 2 dorms are empty.

Inclusion - Exclusion:

$4^{20} - {4\choose 1} 3^{20} + {4\choose 2} 2^{20} - {4\choose 3} 1^{20}$

$\endgroup$

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.