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.

 

[blue_raver22]

I can suggest a few potential approaches to solving this problem. One possible method is to use a mathematical technique called combinatorics, which deals with counting and organizing different combinations of objects. In this case, we can use combinatorics to determine the number of ways to select a specific number of coins from the given set (1, 2, 5, 10, 20, 50, 100) that add up to a total of 200. This would involve using formulas such as permutations or combinations.

Another approach could be to use computer programming to generate all possible combinations and then filter out the ones that do not add up to 200. This may be a more time-consuming method, but it could provide an accurate and comprehensive list of all possible ways to produce 2 bucks from the given set of coins.

Additionally, we could also consider the practical limitations of the problem, such as the availability of certain coins or the physical constraints of carrying a large number of coins. This could potentially narrow down the number of solutions and make the problem more manageable.

In conclusion, there are multiple ways to approach this problem, and further research and experimentation may be needed to find the most efficient and accurate solution. As a scientist, it is important to consider all possible methods and choose the one that best fits the specific problem at hand.