Making up groups of Coins

Question

In how many ways can a group of 100 coins be made up from 50,20,10,5,2 or 1 coin(s) respectively?

An alternative way of phrasing this would be how many ways can a group of 100 coins be made from choosing coins of value 50,20,10,5,2,1? I have tried the problem, and I've realised it is quite difficult to keep track of the arrangements checked (I know the answer is around 4000 though). Can this be solved without a computer?

Answer 1

You will want to use a generating function. For pennies, we can have $1, 2, ..., $ selections. So we have the generating function $f_{1}(x) = 1 + x + x^{2} + ... = \frac{1}{1-x}$. Similarly, with two-cent pieces, we have $f_{2}(x) = 1 + x^{2} + x^{4} + ... = \sum_{i=0}^{\infty} x^{2i} = \frac{1}{1-x^{2}}$. We continue this pattern to get the generating function:

$$f(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^{2}} \cdot \frac{1}{1-x^{5}} \cdot \frac{1}{1-x^{10}} \cdot \frac{1}{1-x^{20}} \cdot \frac{1}{1-x^{50}}$$

You then would want to use something like a computer algebra system to expand out searching for the coefficient of $x^{100}$. Of course, you could theoretically do it by hand, but it would be tedious to do.

Edit: Generating functions work by using a formal geometric series to index terms. So $x^{0}$ says you have none of that term while $x^{53}$ says you have $53$ units. I am using them here to count the number of each coin. Pennies count one unit each, so $f_{1}(x) = \sum_{i=0}^{\infty} x^{i}$ counts the number of pennies you have. In contrast, the five cent pieces count as five units of money. So we have: $f_{5}(x) = \sum_{i=0}^{\infty} x^{5i}$.

By rule of product, we multiply each function together to get the main generating function. We then use geometric series identities to expand out the terms and seek the coefficient of $x^{100}$, which is your desired monetary amount.

This article provides a good look at generating functions too, at least to help conceptualize for you: http://www.dreamincode.net/forums/topic/304589-a-look-at-the-knapsack-problem-with-generating-functions/

Answer 2

I don't think you can find an algorithm to solve the problem that is more efficient than the one for computer which goes like this. You want to find the positive integer solutions to the equation $100a+50b+20c+10d+5e+2f\leq 100$ (Luckily we can simplify the problem slightly because we have $1$ which can take any previous coins up to exactly $100$.

I wrote this code in java, I hope it helps(take into account I just learned to program two weeks ago). Also the code takes into account 200 dollar coins and 100 dollar coins, and it wants to add 200 instead of 100.

public class prob31 {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    int a,b,c,d,e,f,g,h,s=0;
    for(a=0;a<=1;a++){
        for(b=0;b<=(200-200*a-((200-200*a)%100))/100;b++){
            for(c=0;c<=(200-200*a-100*b-((200-200*a-100*b)%50))/50;c++){
                for(d=0;d<=(200-200*a-100*b-50*c-((200-200*a-100*b-50*c)%20))/20;d++){
                    for(e=0;e<=(200-200*a-100*b-50*c-20*d-((200-200*a-100*b-50*c-20*d)%10))/10;e++){
                        for(f=0;f<=(200-200*a-100*b-50*c-20*d-10*e-((200-200*a-100*b-50*c-20*d-10*e)%5))/5;f++){
                            for(g=0;g<=(200-200*a-100*b-50*c-20*d-10*e-5*f-((200-200*a-100*b-50*c-20*d-10*e-5*f)%2))/2;g++){
                                s++;
                                System.out.println(200-200*a-100*b-50*c-20*d-10*e-5*f-2*g);

                                }
                            }
                        }
                    }
                }

            }
        }
    System.out.println(s);
    }


}