Tuesday, March 30, 2010

Bracketology Combinatorics

This is combinatorics, not economics. I suppose this sort of math is useful for political science in calculating power indices.

Consider a single-elimination tournament with 2n teams entered. Ignoring the play-in games, n is six for the NCAA basketball tournament. Some tournaments have "bys" on the first round, and I am ignoring that aspects of those tournaments too.

Let f(n) be the number of ways of filling out your brackets for the tournament. The problem considered here is to calculate f(6).

Since 2n teams are in the tournament, 2n - 1 games are played in the first round. Since there are two possible victors for each game, there are 2(2n - 1) possible ways of filling out your brackets for the first round. The total number of ways of filling out your brackets is then:
f(n) = 2(2n - 1) f(n - 1)
One could guess a closed-form solution for this difference equation and prove it correct by mathematical induction. If I recall correctly, generating functions are useful in finding the solution to such recurrence relations. But, since I am only interested in a few terms, I adopt the brute force calculations shown in Table 1.
Table 1: Tournament Counts
nNumber of
2(2n - 1)Ways of
Filling Out
1222 = 21 = 100.301
2448 = 23 = 100.903
3816 = 24128 = 27 = 102.11
416256 = 28215 = 104.515
532216231 = 109.33
664232263 = 1019.0

Suppose, by some luck of the draw, you correctly chose the 32 winners of all the first round games. There would still be over one billion (109) possible ways of filling out the remainder of the brackets. Even if everybody in the world filled out a bracket for the full tournament, the overwhelming majority of possible brackets would still be unfilled.

No comments: