Hurray For Mathematicians

Over at FiveThirtyEight.com (a great site for political poll junkies) Nate Silver laid down this challenge:

I was asked this question by a highly-respected political writer and couldn't come up with any convenient way to provide him with an answer. Nor does there appear to be any guidance on Google. So let me pose it to the collective:

How many unique ways are there to acquire at least 270 electoral votes without any excess?

For example, one combination would be to win California, Connecticut, the District of Columbia, Hawaii, Illinois, Maine, Massachusetts, Michigan, Minnesota, New Hampshire, New Jersey, New York, Ohio, Oregon, Pennsylvania, Rhode Island, Vermont, Washington and Wisconsin. That would be equal to 272 electoral votes (not coincidentally, these are the John Kerry states plus Ohio).

The first precise and mathematically most elegant solution was given by Isabel Lugo, PhD student in mathematics at our very own University of Pennsylvania.

As you can see, my solution involves a rather large polynomial. The big numbers are confusing, so let's consider a smaller example. Let there be a nation in which there are three states, which have three, four, and five electoral votes respectively. (For the sake of giving things names, I'll call these states Wyoming, Idaho, and Utah respectively.) This nation corresponds to the polynomial

(1 + x^3) (1 + x^4) (1 + x^5)

in an obvious way. Multiplying this out gives

1 + x^3 + x^4 + x^5 + x^7 + x^8 + x^9 + x^12

which tells us that there is one way to pick a set of those states that has zero electoral votes (namely, picking none of them), one way to pick a set which has 3 EV (Wyoming only), etc.

Now, the fact that no set is counted twice here just comes out of the way the multiplication process works. We could write this as

(1 + WY) (1 + ID) (1 + UT)

and then the product is

1 + WY + ID + UT + WY*ID + WY*UT + ID*UT + WY*ID*UT

and if we replace each state's name with x raised to the power of its number of electoral votes, we get back the old polynomial. But you see that WY*ID, for example, occurs only once -- we don't also get ID*WY. The reason for that is because in order to expand the product, we pick either the 1 or the WY from the first factor, either the 1 or the ID from the second factor, and either the 1 or the UT from the third factor.

The actual 51-state solution has the same property, just on a larger scale.

The answer: 51,199,463,116,367, or the sum of the coefficients of x^270, x^271, etc. in a series of similarly constructed polynomials. The real trick is accounting for all of the different classes of cases -- i.e., solutions where the smallest state has three electoral votes, solutions where the smallest state has four, up to and including fifteen (the Georgia, New Jersey, and North Carolina solution).

Update: FiveThirtyEight.com's Nate Silver is now cross-posting at TNR's The Plank, with this heartening distillation:

Overall, our simulations give Obama a 54.4 percent chance of winning the election; this is his highest figure since March 18. As new polling begins to roll in from states like Ohio and Pennsylvania, that lead is likely to get larger before it gets smaller.