Making up groups of Coins 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?
 A: 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/
