2
$\begingroup$

"A grandmother has $10$ identical and indistinguishable gold coins, and she wishes to give all of them away to her $4$ grandchildren: Alice, Bob, Lisa and Michael. In how many different ways can she partition the $10$ coins between her $4 $ grandchildren, giving each $0$ or more coins, such that Alice gets at least $1 $ coin."

The way I would tackle this question would be to assign the fist coin to Alice so we then have $9$ coins to distribute. Then as each coin has $4$ choices I would calculate $4^9$ ways to arrange the distribution of the coins.

However my notes solved a similar question using the fact that $X_1+X_2+X_3+X_4 = 9$ (as the first coin is already assigned) and using the formula $\binom{n+r-1}{n}$ = $\binom{9+4-1}{9}$.

Why is my approach incorrect?

$\endgroup$
3
  • 1
    $\begingroup$ Because your approach assumes the coins are distinguishable. Try it with smaller numbers where you can write out all the possibilities, and you'll see. E.g., 2 children, 2 coins, 3 ways, not 4. $\endgroup$ Aug 19, 2013 at 12:12
  • $\begingroup$ So in other words if we give one coin to Lisa for example then it doesn't matter what coin it is, we only care about the fact that Lisa received one coin? $\endgroup$
    – Kom
    Aug 19, 2013 at 12:15
  • 1
    $\begingroup$ Well, it says the coins are "identical and indistinguishable", so it not only doesn't matter which coins go to which children, it's impossible to tell. $\endgroup$ Aug 19, 2013 at 12:20

2 Answers 2

4
$\begingroup$

The key to the difference is that the coins are indistinguishable. Each child only cares how many coins they get, not which ones. Your answer gives a specific coin to Alice, then keeps track of which coin goes to each child. You are counting AAABBBLLMM as different from AAABBBMMLL and not counting MMLLAAABBB at all. All are the same in giving three coins to Alice, three to Bob, two to Lisa, and two to Mike.

$\endgroup$
1
$\begingroup$

The general solution to problems like this can be solved using the stars and bars technique http://en.m.wikipedia.org/wiki/Stars_and_bars_(combinatorics). See the proof of theorem 2 in this link for the derivation of the general formula of which your problem is a specific case.

$\endgroup$
1
  • 3
    $\begingroup$ That may give a correct way to do the problem, but strictly speaking it doesn't address the question of OP, which was, why was the other approach incorrect? $\endgroup$ Aug 19, 2013 at 12:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .