1
$\begingroup$

If I have $6$ children and $4$ bedrooms, how many ways can I arrange the children if I want a maximum of $2$ kids per room?

The problem is that there are two empty slots, and these empty slots are not unique.

So, I assumed there are $8$ objects, $6$ kids and $2$ empties.

$$C_2^8 \cdot C_2^6 \cdot C_2^4 \cdot C_2^2 = 2520.$$

Subtract off combinations where empties are together:

$$2520 - 4 \cdot C_2^6 \cdot C_2^4 \cdot C_2^2 = 2160$$

Divide by $2!$ to get rid of identical combinations due to identical empties and I get $1080$.

Is this right?

$\endgroup$
  • 1
    $\begingroup$ I assume the children are distinguishable. Are the bedrooms? $\endgroup$ – André Nicolas Jul 17 '14 at 18:59
  • $\begingroup$ Yes, children and bedrooms are distinguishable. $\endgroup$ – Naphtali Jul 17 '14 at 19:06
  • $\begingroup$ 8C2 x 6C2 x 4C2 x 2C2 = 2520 seems wrong, as, different combinations of empties with children can give you different patterns. $\endgroup$ – Juanito Jul 17 '14 at 19:12
0
$\begingroup$

Looks right, given some assumptions. Let's build it up a different way to check your work.

We're basically interested in two patterns of putting kids into rooms. Those are all kids paired with one empty, 2-2-2-0, and two pairs and two solo sleepers, 2-2-1-1. Any other arrangement either breaks the 2 kids max rule or is a permutation of one of these, like 2-1-1-2 or 2-0-2-2. Permutations are easy so let's ignore that for now.

Let's start by figuring out how many unique sets of pairs of kids we can have. There are 15 possibilities for a pair drawn from 6 kids, lettered A-F: AB, AC, AD, AE, AF, BC, BD, BE, BF, CD, CE, CF, DE, DF, and EF. We might now be tempted to take one pair, then figure out the number of combinations for pairs of the remaining four kids for the second pair, and the last two are the third pair. That would give us $C^6_2*C^4_2*C^2_2= 90$ sets of kids.

However, we're double-counting; we could have chosen AB for the first pair and then CD for the second, or vice-versa, and our current calculation assumes AB-CD-EF is different from CD-AB-EF. It's not, so the figure of 90 is $P^3_2 = 6$ times too high; there are actually only 15 unique sets of pairs of all 6 kids that can be formed.

Now, of those 15 sets of pairs, you can either just chuck 'em into rooms, leaving one empty, or you can split any one of the three pairs to form a unique 2-2-1-1 arrangement. So, there are just 60 ways (15 + 3*15) to put 6 kids into 4 rooms with a max of two per room if you don't care who gets what room. If there's an unwritten understanding of one child minimum, no empty rooms, then there are 45 ways just counting the unique 2-2-1-1 arrangements.

Now, if you do care who goes in which room, then there are 24 permutations of 4 things taken 4 at a time. 60 unique ways to split up 6 kids up into 3 or 4 groups, times 24 ways to put those kids into 4 rooms, gives you 1440 unique permutations of kids in rooms if an empty room is allowed. If there must be at least 1 kid per room, then 45 unique 2-2-1-1 patterns, times the same 24 permutations, gives 1080 ways to put kids into specific rooms with at least 1 in each.

QED.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Only possible distributions are (2,2,2,0) and (2,2,1,1). So, total ways=$^4C_1*^6C_2*^4C_2+^4C_2*^6C_2*^4C_2*2=1440$ $\\$ If you do not want to leave any room empty as an added requirement, the only pattern possible is (2,2,1,1), so the answer is 1080. hence, OP is right!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I was also assuming that we didn't want to leave any bedroom empty. Sorry for not being explicit. So I want the second part of your expression: 4C2∗6C2∗4C2∗2 which does equal 1080. $\endgroup$ – Naphtali Jul 17 '14 at 19:23
  • $\begingroup$ So, we are in agreement my friend. $\endgroup$ – Juanito Jul 17 '14 at 19:25
  • $\begingroup$ Brilliant, thank you! $\endgroup$ – Naphtali Jul 17 '14 at 19:27
  • $\begingroup$ Do approve the answer if it satisfies thy query. $\endgroup$ – Juanito Jul 17 '14 at 19:28
0
$\begingroup$

Here is an approach via exponential generating functions. More generally, let's say the number of ways to place $r$ children in the four rooms is $a_r$. Define $$f(x) = \sum_{r=0}^{\infty} \frac{a_r}{r!}x^r$$ In the problem where no room may remain empty, it is evident (after a little thought) that $$f(x) = \left(x + \frac{1}{2!} x^2 \right)^4$$ Expanding the product, we find the coefficient of $x^6$ is $3/2$, so $a_6 = 6! \cdot (3/2) = 1080$.

In the problem where rooms may remain empty, the generating function is just a little different:$$f(x) = \left( 1+ x + \frac{1}{2!} x^2 \right)^4$$ In this case the coefficient of $x^6$ on expansion is $2$, so $a_6 = 6! \cdot 2 = 1440$.

| cite | improve this answer | |
$\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.