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?

  • 1
    $\begingroup$ Are the pockets also distinct? (Your first rephrasing is incorrect because the problem stipulates that you don't need to use all of the coins.) $\endgroup$ Aug 31 '11 at 20:38
  • $\begingroup$ @Qiaochu Yuan:I am not sure of that either,yes I realized it that's why I think of the third summation approach. $\endgroup$
    – Quixotic
    Aug 31 '11 at 20:39
  • 4
    $\begingroup$ The "different model" is incorrect, because it assumes the coins are indistinguishable but the pockets are distinguishable. Whether or not the pockets are distinguishable is unclear, but the problem explicitly says the coins are different, so there are not 8 ways to distribute one coin into the pockets. There's either 5 (if the pockets are all the same; one way for each of the different coins), or there are 40 (if the pockets are different; eight ways for each possible choice of coin). Either way, it's not $8^1$. $\endgroup$ Aug 31 '11 at 20:41
  • $\begingroup$ @Arturo Magidin:May be I am missing something,but we can distribute $1$ distinct items into $8$ distinct groups in $8^1$ (where some groups may be empty) isn't? $\endgroup$
    – Quixotic
    Aug 31 '11 at 20:48
  • $\begingroup$ @FoolForMath: If you have a penny, a nickel, a dime, a quarter, and a half-dollar (5 distinct coins), and you have 8 pockets, in how many ways can you distribute one coin into the pockets? You could have the penny in pocket 1, or pocket 2, or ... or pocket 5; or you could have the nickel in pocket 1, or in pocket 2;... or you could have the dime in pocket 1, or in pocket 2, or... , ..., or you could have the half-dollar in pocket 8. That's 40 different ways. If all the pockets are the same, then you first pick which coin you will be putting into a pocket (5 ways), then put it in. $\endgroup$ Aug 31 '11 at 20:59

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
    $\begingroup$ 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. $\endgroup$ Aug 31 '11 at 21:28

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.