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.

Suppose to have a jar containing 100 coins. I want to count the possibile configuration with pennies, nickels, dimes, quarters and half-dollars.

This is what I have done, but I realized that it's wrong: we have 5 type of labels and we want to label the coins with $k_1,\ldots,k_5$ labels such that $k_1+\cdots+k_5=100$, so what I want to calculate is $\sum_{k_i\geq0,\sum k_i=100}\binom{100}{k_1,\ldots,k_5}$, I calculated that this number is $5^{100}$ (well it's obvious that it's $5^{100}$). But I realized that I'm counting too many objects. Do you have any idea to solve this problem?

share|improve this question

2 Answers 2

up vote 1 down vote accepted

The classical way to look at this is to have $100$ $\circ$s and $4$ $|$s. Each arrangement corresponds uniquely to a choice of coins. The number of $\circ$s before the first $|$ is pennies, the number of $\circ$s between the first and second $|$ is nickels, etc. This gives $\binom{104}{4}$ configurations.

share|improve this answer

The number of vectors of $k$ positive integers whose sum is $n$ is ${n+k-1}\choose{k-1}$. So in this case, $n=100$ an $k=5,$ and your answer is $104\choose 4$.

The way to see this in your case is to write down $104$ circles, then choose 4 of them, and cross those circles out. Now you interpret the number of circles before the first crossed-out one to be the number of pennies. The number of circles remaining between the first and second crossed-out circles is the number of nickles, etc.

share|improve this answer

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.