1
$\begingroup$

The following exercise comes from a book. I do not know how to approach it. I get the sense that it is of the "stars and bars" flavor, but is really a "stars and squares and bars" problem - which is to say one must divide multiple groups of indistinguishable "items", where the groups are distinct from other groups, into distinguishable groups.

I have gotten the answer, but I don't intuitively understand the process of getting it. In particular, I understand that I can use the "multichoose" to get the answer, but I don't fully understand how it breaks down the solution. Help would be appreciated in understanding "why" it works, and "how" it accurately describes the divisions.

The question is as follows:

An elevator starts at the basement with 8 people (not including the elevator operator) and discharges them all by the time it reach the top floor, number 6. In how many ways could the operator have perceived the people leaving the elevator if the 8 people consisted of 5 men and 3 women and the operator could tell a man from a woman? [Modified slightly for readability - two part question but the first part is not too relevant.]

The answer is $${5+6-1 \choose 6}{3+6-1 \choose 6}=14,112$$

in case anyone is wondering.

$\endgroup$
4
$\begingroup$

Let me rephrase the question. You have $8$ balls that are indistinguishable except for color; $5$ of them are blue, and $3$ are red. You have $6$ numbered boxes. You put the $8$ marbles into the $6$ boxes; how many different outcomes can you distinguish?

It’s really just a combination of two simpler problems. First, how many different outcomes for the placement of the blue marbles can you distinguish? That’s a basic stars and bars problem, and the answer is

$$\binom{5+6-1}{6-1}=\binom{10}5=252\;.$$

Similarly, there are

$$\binom{3+6-1}{6-1}=\binom85=56$$

distinguishable outcomes for the red balls. Since any outcome of the blue balls can be combined with any outcome of the red balls, there are altogether $252\cdot56=14,112$ distinguishable outcomes.

Note that although your final numerical answer is correct, your binomial coefficients are not: essentially you’ve interchanged the balls and boxes. You should have either what I used or

$$\binom{5+6-1}5\binom{3+6-1}3\;.$$

The product of your binomial coefficients is only $5880$.

$\endgroup$
  • $\begingroup$ Thank you. Reducing the problem to an "Urn Game" really makes the derivation of the solution clear. Also, treating the men and women as different events and multiplying them to get the total number of combinations was also instructive. $\endgroup$ – d0rmLife Oct 10 '15 at 23:36
  • $\begingroup$ @d0rmLife: You’re welcome. $\endgroup$ – Brian M. Scott Oct 10 '15 at 23:38
  • $\begingroup$ @BrianM.Scott Why do you add 6 to the first binomial coefficient? To account for the fact that each of the 6 urns may have zero balls allocated to it? $\endgroup$ – Caerus Sep 1 '17 at 23:05

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.