In how many ways can I have $1.50 using exactly 50 Coins? In how many ways can I have$1.50 using exactly 50 Coins? The coins may be pennies (1 cent), nickels (5 cents), dimes (10 cents) or quarters (25 cents).

-
There is a solution of this problem, by a method quick and simple enough to do by hand, in the "Generating Functions" chapter of Concrete Mathematics by Graham, Knuth, and Patashnik. It is different from the three solutions below. – MJD Oct 20 '12 at 12:21
In how many ways can this problem be answered? – Graphth Oct 20 '12 at 13:02
Moreover, each and every way will elicit a scowl on the cashier's face when you try to use them to purchase a candy bar! – Michael Joyce Oct 20 '12 at 14:08
As a comparison, if we differentiate arrangements of the coins, there are a lot more ways of arranging the change. Each choice of $x$, $x^5$, $x^{10}$, or $x^{25}$ when expanding the product $$(x+x^5+x^{10}+x^{25})^{50}=\dots+277961174530259752\,x^{150}+\dots$$ corresponds to a particular choice of each of the $50$ coins. The coefficient given above yields the number that total to $\$1.50$. – robjohn Oct 20 '12 at 14:26 7 Answers The total number of ways of forming$1.50 using these coins can be calculated in GAP via:

NrRestrictedPartitions(150,[1,5,10,25]);


which returns 680.

With the additional restriction of there being exactly 50 coins, it can be found via:

NrRestrictedPartitions(150,[1,5,10,25],50);


The 10 possibilities are listed below as [ q, d, n, p ]:

[ 0, 0, 25, 25 ]
[ 0, 4, 16, 30 ]
[ 0, 8, 7, 35 ]
[ 1, 0, 19, 30 ]
[ 1, 4, 10, 35 ]
[ 1, 8, 1, 40 ]
[ 2, 0, 13, 35 ]
[ 2, 4, 4, 40 ]
[ 3, 0, 7, 40 ]
[ 4, 0, 1, 45 ]


The partitions themselves can be computed using: RestrictedPartitions(150,[1,5,10,25],50);

-
Looking at the manual, NrRestrictedPartitions(150,[1,5,10,25],50); is a bit simpler. – Chris Eagle Oct 20 '12 at 12:10
Updated, thanks again! – Douglas S. Stones Oct 20 '12 at 21:38

Let me try a generating function approach (first time trying, apologies if it is wrong):
$f_1=(1+nx+n^2x^2+\dots+n^{150}x^{150})$
$f_5=(1+nx^5+n^2x^{10}+\dots+n^{30}x^{150})$
$f_{10}=(1+nx^{10}+n^2x^{20}+\dots+n^{15}x^{150})$
$f_{25}=(1+nx^{25}+n^2x^{50}+\dots+n^6x^{150})$

The solution can be found within: $g=(f_1)(f_5)(f_{10})(f_{25})$.
More precisely, we need to locate the term $x^{150}n^{50}$, which signifies a sum of $150$ cents and $50$ coins.
Then, the coefficient represents the number of ways to do so.

An explanation of why it works:
For each $f_i$, it can be seen that exponent of $n$ represents the number of coins while exponent of $x$ represents the amount of money.
i.e. $n^5x^{125}$ means 5 coins for 125 cents.
When we multiply two terms, say $(n^ix^j)(n^kx^l)=n^{i+k}x^{j+l}$, it can be seen that the term conveniently computes the sum of money and also sum of coins used.

Calculation by hand is not recommended.
I tried it in Mathematica and I have the term $10n^{50}x^{150}$, which means that there should be 10 ways to do so.

Edit: In view of Soloveichik answer, this is how one might do it in Mathematica:
f=1/((1-n*x)(1-n*x^5)(1-n*x^10)(1-n*x^25));
series=SeriesCoefficient[f,{x,0,150},{n,0,50}]

-
Well done! (+1) Do you see how your answer relates to i. m. soloveichik's answer? – robjohn Oct 20 '12 at 15:44
In your edit, you probably intended $-$ instead of $+$ $$f=\frac1{(1-nx)(1-nx^5)(1-nx^{10})(1-nx^{25})}$$ – robjohn Oct 20 '12 at 15:52
Yes! I have only seen a simple variant of the generating function: $(1+x)(1+x^5+\dots)$ etc. Was wondering how to count multiplicity so I gave it a try. Seems like this is the normal approach. But I am embarrassed to say that I did not know it has to be $-$ though. Learned something today. Thanks for the correction. :) – Yong Hao Ng Oct 20 '12 at 16:23
Indeed, $\frac1{1-x}=1+x+x^2+x^3+\dots$ whereas $\frac1{1+x}=1-x+x^2-x^3+\dots$ – robjohn Oct 20 '12 at 16:27
Oh my, simple series expansion... I see it now. That was silly. =D – Yong Hao Ng Oct 20 '12 at 17:07

In Maple:

$f := \frac{1}{(1-tx)(1-tx^5)(1-tx^{10})(1-tx^{25})}:$

$T := taylor(f, x = 0, 151):$

$T150 := coeff(T, x, 150):$

$coeff(T150,t,50);$

-
Correct, but a little explanation would be nice for those who don't know what you are doing. (+1) – robjohn Oct 20 '12 at 15:50

You are looking for solutions of $$\tag1p+5n+10d+25q=150$$ $$\tag2p+n+d+q=50$$ in non-negative integers $p,n,d,q$.

Any amount $m$ combinable with nickels and dimes is nonnegative and divisible by 5 and uses between $\frac m{10}$ and $\frac m5$ coins. And on the other hand, for any nonnegative amount $m$ divisible by $5$ and $k$ with $5k\le m\le 10k$, there is a unique way to have $m$ cents in $k$ coins that are nickels and dimes. To see this, start with $\frac m5$ nickels and decrease the number of coins one by one (by replacing two nickels with a dime) untl you have the desired number of coins. One observes that this produces $\frac m5-k$ dimes and $2k-\frac m5$ nickels.

Thus we are looking for pairs $(p,q)$ with $p,q\ge0$, such that $150-p-25q$ is a nonnegative multiple of 5 and $5(50-p-q)\le 150-p-25q\le 10(50-p-q)$. The latter inequality is equivalent to $$\tag3 9p-15q\le 350$$ and $$\tag4 4p-20q\ge 100 .$$ Because $150-p-25q$ must be a multiple of $5$, $p$ must be a multiple of $5$. Hence write $p=5p'$. Then (3) and (4) become (after dividing out common factors) $$\tag5 q-3p'\ge -23$$ $$\tag6 p'-q\ge 5$$ And the nonnegativeness of $150-p-25q$ translates to $$\tag 7 -p'-5q\ge-30.$$ From $(5)+3\cdot(6)$, we conclude $-2q\ge -8$, i.e. $q\le 4$ With $q=0$, we obtain $5\le p'\le 7$ from (5) and (6). With $q=1$, we obtain $6\le p'\le 8$. With $q=2$, we obtain $7\le p'\le 8$. With $q=3$, we obtain $8\le p'\le 8$. With $q=4$, we obtain $9\le p'\le 9$. In all cases, (7) holds as well, thus we find a total of $3+3+2+1+1=10$ possible soluitons.

Explicitly, we have the following solutions for $(p,n,d,q)$:

$(25, 25, 0, 0)$, $(30, 16, 4, 0)$, $(35, 7, 8, 0)$, $(30, 19, 0, 1)$, $(35, 10, 4 ,1)$, $(40, 1, 8, 1)$, $(35, 13, 0 ,2)$, $(40, 4, 4, 2)$, $(40, 7, 0, 3)$, $(45, 1, 0, 4)$.

-

Small examples of this sort of problem can be written out. In this case, start with the two equations:

$$p + 5n + 10d + 25q = 150$$ $$p+n+d+q = 50$$

Subtracting, we get:

$$4n + 9d + 24q = 100$$

Notice that since $9$ and $24$ are divisible by $3$ then $100-4n$ must be as well, so $n=3n'+1$ for some $n'$ and we get:

$$12n' + 4 + 9d + 24q = 100$$ or $$4n' + 3d + 8q = 32$$

Now we see that $d$ must be divisible by $4$, so we let $d=4d'$ and we have the equation:

$$n' + 3d' + 2q = 8$$

That is a much easier problem to solve by brute force.

Once you have a solution to this, you have solution to the original by taking:

$$(p,n,d,q) = (50-(3n'+1)-4d'-q, 3n'+1,4d',q)$$

So you need to find all nonegative solutions to: $$n'+3d'+2q = 8$$ with the added condition that $50-(3n'+1)-4d'-q\geq 0$. That last condition turns out to not affect the problem since it is true for all positive solutions.

-

Suppose that you use $p$ pennies, $n$ nickels, $d$ dimes, and $q$ quarters; then $p,n,d$, and $q$ must satisfy the system

\left\{\begin{align*} &p+n+d+q=50\\ &p+5n+10d+25q=150\;. \end{align*}\right.\tag{1}

Thus, you want to count the solutions to $(1)$ in non-negative integers.

The problem is small enough that you can easily solve by hand mostly using brute force. First, subtracting the first equation in $(1)$ from the second gives us the condition $$4n+9d+24q=100\;,\tag{2}$$

from which it’s clear that $q\le 4$.

Suppose that $q=4$; then $4n+9d=100-24\cdot4=4$, which clearly has only the solution $n=1,d=0$. At this point we’ve used four quarters, no dimes, and one nickel, for a total of $105$ cents from $5$ coins, and setting $p=45$ clearly gives the unique solution with $q=4$.

Now suppose that $q=3$, so that $(2)$ reduces to $4n+9d=28$. Clearly $d\le 3$. But both $4n$ and $28$ are divisible by $4$, while $9d$ is not for $0<d\le 3$, so we must have $d=0$ and $n=7$. We’ve now used $10$ coins that total $110$ cents, and it’s clear that setting $p=40$ gives us the unique solution with $q=3$.

Now suppose that $q=2$, so that $(2)$ reduces to $4n+9d=52$. Then $d\le 5$, and we can argue as in the previous case that $9d$ must be a multiple of $4$, so either $d=0$ and $n=13$, or $d=4$ and $n=4$. In the first case we have $15$ coins that total $115$ cents, and we must set $p=35$; in the second we have $10$ coins that total $110$ cents, and we must set $p=40$. These are clearly the only solutions when $q=2$.

If $q=1$, $(2)$ reduces to $4n+9d=76$, so that $d\le 8$. As in the previous two cases we must have $4\mid d$, so $d$ must be $0,4$, or $8$. These lead to the following solutions: $q=1,d=0,n=19,p=30$; $q=1,d=4,n=10,p=35$; and $q=1,d=8,n=1,p=40$.

Finally, if $q=0$, $(2)$ becomes $4n+9d=100$, the feasible values of $d$ are again $0,4$, and $8$, and the resulting solutions are: $q=0,d=0,n=25,p=25$; $q=0,d=4,n=16,p=30$; and $q=0,d=8,n=7,p=35$.

Thus, there are precisely $10$ solutions, and we’ve not just counted them, but also found them.

-

I'm assuming that Douglas' GAP link is probably not easy to understand/implement so here's my explanation.

I'm not sure if there's a good way to solve these change-making problems by hand. The most common solution (that I know of) is algorithmic. Specifically, dynamic programming seems to be a "standard" solution. Since you have an extra constraint of precisely 50 coins you would need to do a bit extra for your DP. In particular, you'd first solve the general problem of the number of ways to form \$1.50 using those coins. Then you'd implement the DP so that you could produce the actual sets of coins that sum to \$1.50 (this is usually just a backtracking step after you finish filling in the memoization table). Finally you can filter those sets by size.

-
So you're assuming the OP understands dynamic programming, and is able to write the code themself, but is unable to install a piece of software and type a command into it? – Chris Eagle Oct 20 '12 at 12:09
I'm answering the question with a student's mindset. I would first see if I could solve it by hand. The next would be to solve it with an algorithm (well, programming it). I guess I have a hard time believing the OP literally just wanted to know that there were 10 ways to do this? – roliu Oct 20 '12 at 12:20