Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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.) –  Qiaochu Yuan Aug 31 '11 at 20:38
    
@Qiaochu Yuan:I am not sure of that either,yes I realized it that's why I think of the third summation approach. –  Quixotic Aug 31 '11 at 20:39
4  
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$. –  Arturo Magidin Aug 31 '11 at 20:41
    
@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? –  Quixotic Aug 31 '11 at 20:48
    
@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. –  Arturo Magidin Aug 31 '11 at 20:59

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
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. –  Tanner Swett Aug 31 '11 at 21:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.