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)

The answer is 242!

Advertisements

Responses

  1. How would you do the first question without the program? How would you figure out the coeifficients?

  2. When the factors of the generating function are all the same (like in the 2nd problem), the multinomial theorem can be used:

    http://en.wikipedia.org/wiki/Multinomial_theorem

    Your best shot for the 1st problem is either 1) buying a TI-89 to expand the polynomial or 2) buying a lot of scratch paper 🙂


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: