# A combinatorial exercise

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?

-

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