## 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.
 n Number ofTeams 2(2n - 1) Ways ofFilling OutBrackets 1 2 2 2 = 21 = 100.301 2 4 4 8 = 23 = 100.903 3 8 16 = 24 128 = 27 = 102.11 4 16 256 = 28 215 = 104.515 5 32 216 231 = 109.33 6 64 232 263 = 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.