sedan
06-12-2008, 06:34 PM
Over at fivethirtyeight.com the math gets pretty intense at times.
A recent thread was devoted to figuring out the exact number of possible ways an electoral college victory could be achieved in the upcoming election. The "winner" was a poster named Isabel Lugo. Her solution:
51,199,463,116,367, which matches nicely with Brian's simulation-based estimate. This is about 2.27% of all the possible combinations.
50,939,354,221,562 of these -- over 99% -- involve at least one 3-electoral-vote jurisdiction. This isn't surprising -- if you pick a set of states at random it's quite likely that it'll include at least one of the 3-EV states, since there are eight of them!
Dynamic programming would work, but I'm a mathematician, not a computer scientist. So my method was as follows: the polynomial (1+x^55)*(1+x^34)*(1+x^31)*(1+x^27)*(1+x^21)^2*(1+ x^20)*(1+x^17)*(1+x^15)^3*(1+x^13)*(1+x^12)*(1+x^1 1)^4*(1+x^10)^4*(1+x^9)^3*(1+x^8)^2*(1+x^7)^4*(1+x ^6)^3*(1+x^5)^5*(1+x^4)^5*((1+x^3)^8-1)
has as its coefficient of x^n the number of sets of states which add up to n electoral votes, which includes at least one 3-EV state. This basically follows from the process of multiplication. It's easy to get a computer algebra system to expand this (I use Maple) and extract the coefficients of x^270, x^271, and x^272; adding these together gives the total number of ways to get 270, 271, or 272 electoral votes using at least one 3-EV state, which is the smaller of the two numbers above.
Removing the ((1+x^3)^8-1) factor, and replacing the second-to-last factor with (1+x^4)^5-1, then allows us to consider the states which have four or more electoral votes. We take that polynomial and extract the coefficients of x^270, x^271, x^272, and x^273 -- adding those together gives the total number of ways to get 270, 271, 272, or 273 electoral votes using no 3-EV states and at least one 4-EV state.
Repeat for the cases where the smallest state is a 5-EV state, a 6-EV state, ..., a 15-EV state, add those up, and that gives the answer.
When another poster remarked that her solution was elegant, Isabel replied:
well, I should hope I'm able to do this -- I've taken more courses in combinatorics than I care to count. :)
http://www.fivethirtyeight.com/2008/06/homework-assignment.html
A recent thread was devoted to figuring out the exact number of possible ways an electoral college victory could be achieved in the upcoming election. The "winner" was a poster named Isabel Lugo. Her solution:
51,199,463,116,367, which matches nicely with Brian's simulation-based estimate. This is about 2.27% of all the possible combinations.
50,939,354,221,562 of these -- over 99% -- involve at least one 3-electoral-vote jurisdiction. This isn't surprising -- if you pick a set of states at random it's quite likely that it'll include at least one of the 3-EV states, since there are eight of them!
Dynamic programming would work, but I'm a mathematician, not a computer scientist. So my method was as follows: the polynomial (1+x^55)*(1+x^34)*(1+x^31)*(1+x^27)*(1+x^21)^2*(1+ x^20)*(1+x^17)*(1+x^15)^3*(1+x^13)*(1+x^12)*(1+x^1 1)^4*(1+x^10)^4*(1+x^9)^3*(1+x^8)^2*(1+x^7)^4*(1+x ^6)^3*(1+x^5)^5*(1+x^4)^5*((1+x^3)^8-1)
has as its coefficient of x^n the number of sets of states which add up to n electoral votes, which includes at least one 3-EV state. This basically follows from the process of multiplication. It's easy to get a computer algebra system to expand this (I use Maple) and extract the coefficients of x^270, x^271, and x^272; adding these together gives the total number of ways to get 270, 271, or 272 electoral votes using at least one 3-EV state, which is the smaller of the two numbers above.
Removing the ((1+x^3)^8-1) factor, and replacing the second-to-last factor with (1+x^4)^5-1, then allows us to consider the states which have four or more electoral votes. We take that polynomial and extract the coefficients of x^270, x^271, x^272, and x^273 -- adding those together gives the total number of ways to get 270, 271, 272, or 273 electoral votes using no 3-EV states and at least one 4-EV state.
Repeat for the cases where the smallest state is a 5-EV state, a 6-EV state, ..., a 15-EV state, add those up, and that gives the answer.
When another poster remarked that her solution was elegant, Isabel replied:
well, I should hope I'm able to do this -- I've taken more courses in combinatorics than I care to count. :)
http://www.fivethirtyeight.com/2008/06/homework-assignment.html