How many different ways are there to make n dollars with 1, 5, 10, 25, and 50 cent coins.

Question

I am trying to figure out a formula for how many different ways you can make n American dollars with pennies, nickels, dimes, quarters, and half dollars. There has to be a formula for this, right? I really don't want to make a huge list of the different ways to make 4 dollars (according to my teacher, there are 26517 ways). Also, I am looking for formulas that are easy to understand as a freshman in high school. I realize I should have specified this before, and I am sorry for those who have spent time and effort in answering my question, only for me to not understand it.

Answer 1

With the edit to the question, you want the coefficient of $x^{400}$ in the expansion of $\frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})}$ and is indeed $26517$. But I suspect you are expected to find it another way. Here is one approach.

Let $f(n,m)$ be the number of ways of making $n$ using the $m$ smallest coins, so for example $f(11,2)=3$ is the number of ways of making $11$ cents with $1$ and $5$ cent coins since you can have $5+5+1$ or $5+1+1+1+1+1+1$ or $1+1+1+1+1+1+1+1+1+1+1$. You could find this as adding a $5$ cent coin to an existing pattern for $6$ cents, or simply use a pattern for $11$ cents without any $5$ cent coin, i.e. $f(11,2)=f(6,2)+f(11,1)=2+1=3$. Then you have:

• $f(n,m)=0$ for $n <0$ or $m <0$
• $f(0,0)=1$ for $m \ge 0$ since there is one way of making $0$ cents
• $f(n,0)=0$ for $n>0$ since you would have no coins
• $f(n,1)=f(n-1,1)+f(n,0)$ for $n\ge 0$
• $f(n,2)=f(n-5,2)+f(n,1)$ for $n\ge0$
• $f(n,3)=f(n-10,3)+f(n,2)$ for $n\ge0$
• $f(n,4)=f(n-25,4)+f(n,3)$ for $n\ge0$
• $f(n,5)=f(n-50,5)+f(n,4)$ for $n\ge0$

and you want $f(400,5)$

Answer 2

Let us start from the generating function:

$$f(x)=\frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})(1-x^{50})}=\sum c_nx^n\tag{1}$$ with

$c_n = \text{number of ways to get the change for $n$ cents with available coins} 1,5,10,25,50 \text{cts.}$

You want to obtain $c_{400}$.

Here is a specific way permitting to obtain a direct answer, without having to compute other coefficients $c_n$.

I am going to develope a method that I would describe as closer to Numerical Analysis than to an algorithmic approach.

It uses theoretical properties about complex function theory.

Let us consider:

$$g_n(z):=\dfrac{f(z)}{z^{n+1}} \ = \ \text{polynomial} \ + \ \dfrac{c_n}{z}+\dfrac{c_{n+1}}{z^2}+\cdots\tag{2}$$

If you know complex function theory, the integral of $g_n(z)$ along a path $\gamma$ enclosing pole $z=0$ and uniquely this pole (see remark below), will be equal to $2i \pi c_n$ ($c_n$ is the residue at pole $0$). Otherwise said :

$$c_n=\dfrac{1}{2 i \pi} \int_{\gamma} g_n(z) dz\tag{3}$$

Let us now use a good integration "blackbox", like that of Matlab ;

n=400;r=0.99;v=12; 
gamma=r*exp(i*2*pi*(0:(v-1))/v); % int. path = polygon with v vertices
g=@(z)(1./((z.^(n+1)).*(1-z).*(1-z.^5).*(1-z.^10).*(1-z.^25).*(1-z.^50)));
integral(g,r,r,'Waypoints',gamma)/(2*pi*i) 

giving almost instantly $c_{400}=26517$.

More exactly: $26517 + 3.6.10^{-8}i$... Please note the very small "perturbation" along the imaginary axis.

Important remark : Set apart pole $0$, all other poles of $g$ belong to the unit circle (because they are roots of unity). Choosing as integration path $\gamma$ a polygon interior to the unit circle ensures that no other pole is inside $\gamma$. The choice of the polygonal path is up to us. But it must be chosen very close to the unit disk because the huge power $x^{401}$ present in the denominator of $g_{400}$ (see relationship (2)) to prevent the risk of having an almost-division-by-zero !