Counting Pennies, Generating Functions and STEP

STEP I 1997, Question 1
Show that you can make up 10 pence in eleven ways using 10p, 5p, 2p and 1p coins.

In how many ways can you make up 20 pence using 20p,10p 5p, 2p and 1p coins?

There is an interesting way of approaching this question using generating functions.

A generating function is of the form:

a_{0}+a_{1}t+a_{2}t^{2}+a_{3}t^{3}+\dots

where the coefficients of t count various problems and issues of convergence are unimportant.

Show that you can make up 10 pence in eleven ways using 10p, 5p, 2p and 1p coins.

This will be the co-efficient of t^{10} in,

(1+t+t^{2}+t^{3}+\dots+t^{10})(1+t^{2}+t^{4}+\dots+t^{10})(1+t^{5}+t^{10})(1+t^{10})

by way of explanation:

\overset{\textnormal{the 1p s}}{\overbrace{(1+t+t^{2}+t^{3}+\dots+t^{10})}}\overset{\textnormal{the 2p s}}{\overbrace{(1+t^{2}+t^{4}+\dots+t^{10})}}\overset{\textnormal{the 5p s}}{\overbrace{(1+t^{5}+t^{10})}}\overset{\textnormal{the 10p s}}{\overbrace{(1+t^{10})}}

The candidate still needs to expand the function to get the answer, but having changed the problem to one of algebra, they might enjoy the benefits of practice and familiarity in the manual computation.

For those of at liberty to explore the question at leisure, a Computer Algebra System (CAS) is useful. In fact, the website Wolfram Alpha will expand the brackets for us, computing the answers to all similar counting problems in the process. The Wolfram Alpha query box understands the latex code if this is just pasted in, but only if it is presented in an explicit form, that is without the dots.  In order to simplify the question for the CAS notice that each bracket is a geometric progression, which can be summed using standard A level theory reducing the function to:

\dfrac{(1-t^{11})}{(1-t)}\dfrac{(1-t^{12})}{(1-t^{2})}\dfrac{(1-t^{15})}{(1-t^{5})}\dfrac{(1+t^{10})}{1}

Use of Wolfram Alpha then gives the following:

190218GenratingPennies1

which contains our answer to the first part: 11.

Equipped with some methods and machinery we can now proceed to the second part of the question.  In fact, we can adapt the method and functions to count any similar loose change problem.

In how many ways can you make up 20 pence using 20p,10p 5p, 2p and 1p coins?

This will be the coefficient of t^{20} in,

(1+t+t^{2}+t^{3}+\dots+t^{20})(1+t^{2}+t^{4}+\dots+t^{20})(1+t^{5}+t^{10}+\dots+t^{20})(1+t^{10}+t^{20})(1+t^{20})

\overset{\textnormal{the 1 p s}}{\overbrace{(1+t+t^{2}+t^{3}+\dots+t^{20})}}\overset{\textnormal{the 2 p s}}{\overbrace{(1+t^{2}+t^{4}+\dots+t^{20})}}\overset{\textnormal{the 5 p s}}{\overbrace{(1+t^{5}+t^{10}+\dots+t^{20})}}\overset{\textnormal{the 10p s}}{\overbrace{(1+t^{10}+t^{20})}}\overset{\textnormal{the 20p s}}{\overbrace{(1+t^{20})}}

which is equal to

\dfrac{(1-t^{21})}{(1-t)}\dfrac{(1-t^{22})}{(1-t^{2})}\dfrac{(1-t^{25})}{(1-t^{5})}\dfrac{(1+t^{10}+t^{20})(1+t^{20})}{1}

and which Wolfram Alpha gives and expansion of:

190218GenratingPennies2

and our answer: 41.