Ways to produce specific value out of limited set

[martix]

I have this infuriating little problem I'm trying to solve:
How many ways are there to produce 2 bucks out of any number of coins?

So this means - how many ways to get 200 by adding 1, 2, 5, 10, 20, 50, 100.

The best idea I could come up with so far in my research was counting multisets, but that didn't get me very far.

 

[micromass]

It is for such a problems that generating functions are useful.

I would take a look in the great book "concrete mathematics" by Graham, Knuth and Patashnik.

I'll solve the following easier problem:
How many ways to get 50 out of 1 and 5.

Let's first assume that we have nothing but pennies (denotes by p). The sum of all ways to leave some number of pennies in change can be written as

X=1+p+p^2+p^3+...

thus the 1 means that we leave no pennies, the p means we leave 1 penny, etc.

Now, if we're also allowed to use nickels (denotes by n), then the number of ways we can leave change is

Y=X+nX+n^2X+n^3X+...

the X means we leave a number of pennies and no nickels, the nX means we leave one nickel, etc. Obviously

Y=(1+n+n^2+n^3+...)X=(1+n+n^2+n^3+...)(1+p+p^2+p^3+...)

This product contains terms like nnnpppp, which means we leave 3 nickels and 4 pennies. Now, we use a little trick, we exchange p with z and n with z^5, we get

Y=(1+z+z^2+z^3+...)(1+z^5+z^{10}+z^{15}+...)

We are actually interested in z^{50} in this product, since the coefficient will tell us the number of ways we can pay 50.

Now the generating functions come into the play. These give us that

\frac{1}{1-z}=1+z+z^2+z^3+...~\text{and}~\frac{1}{1-z}=1+z^5+z^{10}+z^{15}+...

Thus,

X=\frac{1}{1-z}~\text{and}~Y=\frac{X}{1-z^5}

or equivalently

(1-z)X=1~\text{and}~(1-z^5)Y=X

Now, we can find the coefficient of z^n by following recurrence relations: (denote the coefficient of zⁿ in X (resp. Y) as X_n (resp. Y_n). Then we get

X_n=X_{n-1}~\text{and}~Y_n=Y_{n-5}+X_n.

Thus, for n=50, we get

Y_{50}=Y_{45}+X_{50}=Y_{40}+X_{45}+X_{50}=...=Y_0+X_5+X_{10}+X_{15}+...+X_{50}.

Now, it is easy to see that X_n=1 and that Y_0=1, thus we get

Y_{50}=10

So there are 10 ways of paying.Note, that there are ways to give clean closed-form formulas of Y_n. But I won't give them here. For that, I should read the book Concrete mathematics...

 

[awkward]

Like micromass, I am a big fan of generating functions as discussed in "Concrete Mathematics".

The classic problem along these lines is "How many ways can you make change for a dollar?" If you would like to see an approach that doesn't use generating functions, see this link:

http://mathforum.org/library/drmath/view/57912.html

 

[gb7nash]

Generating functions are very powerful if you want to count things. If you can get the time to learn them, I would suggest it.