How should the teams be arranged in a “seeded” single-elimination tournament bracket?
This question is motivated by the NCAA men’s basketball tournament, the first two rounds of which are now in the books. There are 64 teams in the tournament, divided into four regions each with 16 teams seeded #1 through #16. In typical displays of these regional brackets, such as those on the NCAA and ESPN web sites, the 16 seeds in a region are arranged as shown at left in the figure below, where in this example the favored seed always wins, advancing to the right with each round of the tournament:
The basic idea behind this arrangement is that all of the best-seeded teams should be able to advance together for as many rounds as possible, with more advantage granted to higher seeds. More precisely, we want a tournament bracket with rounds to be fair, defined recursively as follows: the match-ups between the
teams must be arranged with seed
playing seed
in the current round, so that assuming the favored seed wins each game, seeds
can all advance to the next round, and the remaining bracket is (recursively) also fair.
The above bracket layout has a few visually appealing properties:
- In the first round, the favored seed is always the “visiting” team, placed above the lower-seeded opponent.
- The #1 seed is always at the top of the bracket in each round.
- The #2 seed is (almost, except for property 1) as far from the #1 seed as possible, so that the two top-seeded teams clearly advance “toward” each other in each round.
But this isn’t the only possible fair bracket layout. It’s an interesting problem to count them all. (Hint: even constrained by all three properties above, there are still four different possible layouts, of which the above is just one example.)
For example, consider the following layout, which motivated this post:
This layout is the one that I used to store the history of all past NCAA tournaments since 1985 in the current 64-team format. The layout has the first two properties above, but not the third. I chose it because it’s easy to implement; the following simple Python function generates the ordering of seeds, effectively starting from the single #1 seed as the champion on the right of the bracket and moving left through previous rounds, maintaining the fairness condition as we go:
def bracket_seeds(num_teams): seeds = [1] while len(seeds) < num_teams: games = zip(seeds, (2 * len(seeds) + 1 - seed for seed in seeds)) seeds = [team for game in games for team in game] return seeds
This layout has another “nice” structural interpretation as well: if we temporarily re-index the seeds to start with zero instead of one, then the positions of each seed in the bracket are given by the bit-reversed Gray codes of the seeds.
So, back to the original puzzle: what similarly “nice” algorithm yields the more common layout used by the NCAA, ESPN, etc.? More generally, what other “nice” algorithms yield yet other alternative fair layouts? For example, PrintYourBrackets.com seems to use the same approach that I did, generating the same layout for brackets with 4, 8, and 16 teams… but the 32-team bracket is different.