[Math] Combinations of distinct vs identical objects

combinatorics

  1. A child has 5 pockets and 4 marbles. In how many ways can he put the marbles in his pockets?

  2. In how many ways can 11 identical apples be distributed among 6 children so that each child receives at least one apple?

My approach is as follows:

1) for every marble, say M, i have 5 options for pockets (P P P P P), hence i get 5*5*5*5=5^4. This is the correct answer.

2) However, i am unable to apply the same concept to the second problem. i distribute 6 apples to 6 children therefore fulfilling the "at least one apple" condition. Then i am left with 5 apples. For each apple, i have 6 options, hence by this logic i get 6*6*6*6*6=6^5. However this is wrong as i am unable to account for identical objects.

Please point out where i am missing. I don't understand the logic behind n+r-1Cr-1 or n-1Cr-1.

Best Answer

If the marbles are all distinct, then your analysis for the first problem is right. (If the marbles are identical, then the number of ways is $\binom{8}{4}$.)

Let's look at the second problem. We have $11$ identical apples. Line them up like this: $$A\quad A \quad A\quad A \quad A \quad A \quad A \quad A \quad A\quad A \quad A,$$ with a gap between consecutive apples. There are $10$ interapple gaps. We will do our distribution as follows. We will choose $5$ of these gaps to put a separator (say a grape) into. Child $1$ will get all the apples from the leftmost one to the first grape. Child $2$ gets all the apples from the first grape to the second grape. Child $3$ will get all the apples from the second grape to the third, and so on. Finally, Child $6$ gets all the apples from the fifth grape to the right end.

There are exactly as many ways to distribute the apples between the kids as there are to place $5$ grapes as described above. For if we know how many apples each of the kids gets, we know where to place the grapes. Also, as we saw above, every grape placement determines what each child gets. It follows that the number of ways to distribute the apples is $\binom{10}{5}$.

Remark: For completeness, we deal with the marble problem on the assumption marbles are identical. The idea is similar to the apple one, but with a twist. We want to distribute $4$ marbles between $5$ pockets (children). What is different is that we are not asking that each child get a marble.

Imagine doing the distribution as follows. We will distribute $9$ marbles among $5$ children, so that each child gets at least one marble. Then we take away a marble from each child. We will end up with $4$ marbles distrbuted among $5$ children.

Use the separator idea. There are $\binom{8}{4}$ to distribute $9$ identical marbles between $5$ children, with each child getting at least one marble. So there are $\binom{8}{4}$ ways to distribute $4$ marbles among $5$ children.

Actually, with pockets and identical marbles, the numbers are small enough that we could count more crudely. We could put all the marbles in one pocket. There are $\binom{5}{1}$ ways to do this. We could put $4$ marbles in one pocket and $1$ in another. The lucky pocket can be chosen in $\binom{5}{1}$ ways, and for each of these, the pocket that will have one marble can be chosen in $\binom{4}{1}$ ways, for a total of $\binom{5}{1}\binom{4}{1}$. Continue.

Related Question