Single-Elimination Tournament Bracket Count
A single-elimination tournament has $N$ teams (where $N$ is a power of 2). In each round, teams are paired up, and the loser of each match is eliminated. This continues until one champion remains.
A "bracket" specifies which teams play each other in the first round, and how the winners are matched up in subsequent rounds. Two brackets are different if any first-round matchup differs, or if the way winners feed into later rounds differs.
How many distinct tournament brackets are possible for $N$ labeled teams?
Hints
- Think of the bracket as a binary tree with teams at the leaves. How many ways can you assign teams to leaf positions?
- At each internal node of the tree, swapping the left and right subtrees produces the same matchups. How many such symmetries are there?
- There are $N!$ leaf assignments and $2^{N-1}$ symmetries from the $N-1$ internal nodes, giving $N!/2^{N-1}$ distinct brackets.
Worked Solution
How to Think About It: A single-elimination bracket is really just a full binary tree with $N$ leaves, where you assign teams to the leaves. The tree structure determines who can potentially meet whom and in which round. The key insight is that a bracket is defined by its matchups, and swapping the left and right children of any internal node gives you the same set of matchups -- it does not matter which side of the bracket a team is drawn on, only who they face.
Quick Estimate: Start small to build intuition. With $N = 2$: one match, one bracket. With $N = 4$ teams $\{A, B, C, D\}$: the possible first-round pairings are $\{AB, CD\}$, $\{AC, BD\}$, $\{AD, BC\}$ -- that is 3 brackets. Notice $4! / 2^3 = 24/8 = 3$. With $N = 8$: $8! / 2^7 = 40320 / 128 = 315$. The pattern is $N! / 2^{N-1}$.
Approach: Count the total number of ways to assign $N$ labeled teams to the leaves of a complete binary tree, then divide out the symmetries (left-right swaps at each internal node).
Formal Solution:
- Fix a complete binary tree with $N$ leaves and $N - 1$ internal nodes. There are $N!$ ways to assign the $N$ labeled teams to the $N$ leaf positions.
- However, at each internal node, swapping the left and right subtrees produces the same matchups -- the two teams in a match play each other regardless of which is "on the left." Since there are $N - 1$ internal nodes, each with an independent left-right symmetry, there are $2^{N-1}$ arrangements that correspond to the same bracket.
- Therefore the number of distinct brackets is:
$$\text{Brackets}(N) = \frac{N!}{2^{N-1}}$$
Verification with small cases: - $N = 2$: $2!/2^1 = 1$. One match, one bracket. - $N = 4$: $4!/2^3 = 3$. The three ways to partition four teams into two first-round pairs. - $N = 8$: $8!/2^7 = 315$. - $N = 16$: $16!/2^{15} = 638,512,875$.
Answer: The number of distinct single-elimination tournament brackets for $N$ labeled teams is $\dfrac{N!}{2^{N-1}}$.
Intuition
The core idea is an overcounting-then-symmetry argument that shows up constantly in combinatorics. You start by counting a structured arrangement (assigning labeled teams to tree leaves), then divide out the symmetries that produce identical outcomes. Here the symmetry is simple: in any match, it does not matter which team is "home" or "away," so swapping the two sides of any pairing does not create a new bracket. Since this swap is independent at each of the $N - 1$ internal nodes, you divide by $2^{N-1}$.
This same pattern -- count labeled arrangements, divide by a symmetry group -- appears throughout quant work. Counting distinct partitions of a portfolio into groups, enumerating non-redundant hedging strategies, or figuring out how many distinct ways a matching engine can pair off $N$ orders all use the same logic. The lesson: whenever you see "how many distinct ways," ask yourself what the symmetry group is and use Burnside or simple division to remove the overcounting.