Counting with Polynomials

This is to expand on a recent comment I made to “Factoring non-monic quadratics.”

We hear a lot these days about “modeling with mathematics.”  One aspect of this is the use of formal calculations as a modeling device.  An example, pretty common in many high school programs, is the use of the binomial theorem to compute combinations.  So, you can use (t+h)^{10} to compute the number of ways that you can get, say, 4 heads and 6 tails when you toss a fair coins 10 times.   Another example is when you use powers of a matrix to get Fibonacci numbers.  The calculations not only give you answers, they let you derive properties of the phenomena they model.

One of my favorite uses of formal calculations comes from a project that my daughter gave to her sixth grade class some year ago: compute the most likely sum (and the distribution of sums) when several dice are thrown.  For two dice, the problem is fairly standard, and most kids make a 2 by 2 table of all possibilities.  For three dice, her students invented all kinds of clever representations, some very algebraic — not in notation, but in spirit.  This triggered an idea that has become a recurring theme in our high school program.  It goes like this:

If you use expansion boxes to multiply polynomials, you see that the expansion of


contains exactly the same numbers as the 2-dimensional table that records the possible outcomes when you roll two dice.  In other words, the number of ways of rolling a 5 when you throw two dice is the coefficient of x^5 in


It’s the number of ways you can make 5 as a sum of two integers, each between 1 and 6.  The same reasoning shows that the coefficient of x^k in


gives the number of ways you can roll a k when m dice are thrown.

From here, you can use the structure of the expression (x+x^2+x^3+x^4+x^5+x^6)^m
to get results about the distribution of sums.  For example:

  • There are 6^m possible sums, because this is the sum of the coefficients, and the sum of the coefficients comes from putting x=1
  • There are as many even sums as odd sums (replace x by -1).
  • The distribution of sums on three dice whose faces are labeled \{0, 2, 3, 4, 5, 5\}, \{0, 1, 1, 2, 2, 2\}, \text{and} \{1, 2, 3, 6, 6, 6\} can be read off from the coefficients of the product of three different polynomials.
  • Various factorizations of (x+x^2+x^3+x^4+x^5+x^6)^m give you different information about the distributions.  One interesting thing to try is to rearrange the factors of (x+x^2+x^3+x^4+x^5+x^6)^2 to try and produce two dice, different from the standard ones, whose distribution is the same as the standard distribution.  (This may or may not be possible, we’re not telling.)

All this is a preview, accessible to high school students, of the incredibly useful field of algebraic combinatorics and generating functions.