2
$\begingroup$

I have 6 distinguishable balls I want to put into 4 distinguishable boxes stacked on top of each other. The restriction is that the lower box must contain at least one, and the upper box must contain exactly one.

My solution is: there are 6 different ways to fill the upper box. after that, there are 5 different ways to fill the lower box. after that, the third ball can be put into 3 boxes (i.e. all but the upper one), and so on for the fourth, fifth and sixth balls. so my solution is: $6 * 5 (3 * 3 * 3 * 3) $

Am I correct? I've searched so much for such problems and couldn't understand most of the answers. My knowledge is limited to factorials, n choose k, permutations and complementary events.

$\endgroup$
4
$\begingroup$

You started out fine with the initial factor of $6$ for filling the top box, but then you overcounted. If the bottom box ends up with two balls, for instance, you’ve counted it twice, once with each of the two as the one that you figured into the factor of $5$.

This is a small enough problem that it’s probably easiest to go for the specific solution and not try to get too general. After you fill the top box, you can put $1,2,3,4$, or $5$ of the remaining balls into the bottom box. Treat each case separately.

  • There are $5$ ways to choose one ball for the bottom box. Now you have $4$ balls to distribute between the middle two boxes. In effect you’re counting functions from a $4$-element set (the balls) to a $2$-element set (the middle boxes); you’re making a $2$-way choice $4$ times, once for each ball, so you can do it in $2^4=16$ ways. Thus, there are $6\cdot5\cdot16=480$ distributions with one ball in the bottom box.

  • There are $\binom52=10$ ways to choose two balls for the bottom box. Now you have $3$ balls to distribute between the middle two boxes. The same reasoning as before shows that there are $2^3=8$ ways to do this, so there are $6\cdot10\cdot8=480$ distributions with two balls in the bottom box.

I’ll leave the remaining three cases to you; they’re all pretty similar.

$\endgroup$
2
$\begingroup$

Certainly it's best to pick a ball for the top box and then ignore it for the remainder of the process, multiplying any result there by those $6$ starting options.

After that we could consider the situation where there's no restriction on the bottom box. In that case, each balls that comes up for distribution has a choice of three boxes, and the result of this stage would be $3^5$. However there is a restriction that requires the bottom box not be empty. So how many options leave the bottom box empty? In that case there are just two options for each ball and the result of the 5-ball stage would be $2^5$. So we can subtract that off and get the full answer: $$6(3^5-2^5)=6(243-32) = 6\cdot 211 = 1266$$

$\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.