0
$\begingroup$

In how many ways can some or all of the $5$ distinct coins be put into $8$ pockets?

Could this be modeled as the problem of "In how many ways N distinct items be put into r distint groups (where some groups may be empty)?"

My instructor is of the opinion that this problem should be modeled as like for every coin we have $9$ options to put it into one of the 8 pockets or don't and so the answer is $9^5$,however in this case I think $-1$ is necessary to avoid the case when none is selected but he thinks we don't need that.

There is also a different model that I think could be the solution which is as a summation of $8^1 + 8^2 + \cdots + 8^5$ pertaining to how many ways $1$ coin could be distributed in $8$ pockets then $2$ coins in $8$ pockets ... till $5$ coins in $8$ pockets.(assuming pockets are distinct in every case)

But as the answer is not given I can't be sure which is correct,(instructor haven't disclosed it either),could any body tell me which one is correct,if none is correct,then how exactly I am supposed to count this?

  • 0
    @Arturo Magidin:That's clears things for me,thank you:-)2011-08-31

1 Answers 1

6

If I understand correctly, for each of $\binom{5}{k}$ choices of $k$ coins, you will have $8^k$ maps from those $k$ coins to the $8$ pockets. If that is the case, then the answer would be $ \sum_{k=0}^5\binom{5}{k}8^k = (1+8)^5 $ by the binomial theorem.

Another way of looking at this, is to add a ninth hidden pocket for the coins that don't appear in the visible $8$ pockets. That is, you are asking how many ways to put $5$ coins into $9$ pockets, or $9^5$.

If you don't want to allow $8$ empty (visible) pockets, then the answer would be $9^5-1$.

  • 2
    Whether or not you need to subtract one is a matter of whether or not zero counts as "some or all". I would say that zero is not some, and zero is not all, so you should subtract one, but if your instructor says otherwise, there's not much you can do apart from frowning.2011-08-31