3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.