Confused about how to solve basic combinatorial problem

4.1k Views Asked by At

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.

1

There are 1 best solutions below

3
On BEST ANSWER

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