Posted by: rfgarcia | December 6, 2008

## Neat Counting Technique

I learned this back in high school, but Henrik’s post about making change reminded me of it. I also used this technique with Sandeep for a project in Applied Math 115 a few weeks ago. The technique involves a concept called generating functions, and it’s useful for answering questions like

1) How many ways are there to make change for a dollar (using 1c, 5c, 10c, and 25c coins)?
2) How many ways are there to roll two dice so that the sum of the faces is 4? What about for any number of dice and any sum?

The second problem is easier to demonstrate, so I’ll answer it first. First, consider the following polynomial expression and its expansion:

$(x+x^2+x^3+x^4+x^5+x^6)(x+x^2+x^3+x^4+x^5+x^6) =$
$x^2+2x^3+3x^4+4x^5+5x^6+6x^7+5x^8+4x^9+3x^{10}+2x^{11}+x^{12}$

If you think about the exponents in the first and second factors as representing the respective outcomes of the first and second die,  then the coefficient of $x^n$ in the expansion counts the number of ways of achieving a sum of $n$ when rolling 2 dice. So the number of ways to roll a sum of 4 is given by the coefficient on $x^4$, which is 3. This can be verified by counting the factors that lead to $x^4$:

$x \cdot x^3$
$x^2 \cdot x^2$
$x^3 \cdot x$

Generalizing to any number of dice involves adding more factors of $(x+x^2+x^3+x^4+x^5+x^6)$, and probably the help of a computer algebra system like Mathematica, Maple, or Matlab.

The first problem can be solved by creating a generating function where each factor represents the number of coins of a specific denomination that we use in making change for a dollar. For example, there are ways to make change for a dollar that involve the use of anywhere from 0 to 4 quarters, so one factor will be

$(1+x^{25}+x^{50}+x^{75}+x^{100})$

Similarly, we can use anywhere from 0 to 10 dimes:

$(1+x^{10}+x^{20}+...+x^{100})$

anywhere from 0 to 20 nickels:

$(1+x^{5}+x^{10}+...+x^{100})$

and anywhere from 0 to 100 pennies:

$(1+x+x^{2}+...+x^{100})$

The coefficient on $x^{100}$ in the product of all four of these factors gives the number of ways to make 100 cents with any combination of pennies, nickels, dimes, and quarters. The following snippet of Matlab code does the expansion:

nickels = zeros(1,101); dimes = zeros(1,101); quarters = zeros(1,101);
pennies = poly2sym(ones(1,101));
nickels(1:5:101) = 1; nickels = poly2sym(nickels);
dimes(1:10:101) = 1; dimes = poly2sym(dimes);
quarters(1:25:101) = 1; quarters = poly2sym(quarters);
result = expand(pennies*nickels*dimes*quarters);
result = sym2poly(result);
result(101)