0

Say I have $4$ teams, then what are all the possible bracket possibilities. I know the number of possibilities exponentially increases with the more teams in the bracket. If there are any websites that could help, that would be great too.

lightningjay
  • 278
jeff
  • 1
  • Please explain what you mean by "all the possible bracket possibilities." What is a "bracket possibility?" – saulspatz Apr 10 '18 at 14:50
  • if i create my own bracket of 4 teams, A plays B, C plays D, and then both winners play, how many different bracket combinations can be made. Not just (x-amount of ways), but id like to know how to create all the possible ways to create the bracket. – jeff Apr 10 '18 at 14:52
  • either the manual process, or using excel preferably – jeff Apr 10 '18 at 14:53
  • Is this just one bracket: A vs B, C vs D, or do you take the outcomes of the games into account? – saulspatz Apr 10 '18 at 14:54
  • find the number of games and the number of possible outcomes (brackets) will be $\large{2^{total number of games}}$ – Vasili Apr 10 '18 at 14:55
  • i take the outcome of the games into account. I would like to create all the possible ways a bracket can be made. i know how to get the number of ways, but i would like to learn the process on how to get that number. – jeff Apr 10 '18 at 14:57
  • each game has 2 possible outcomes, that's why you if you have two elimination rounds and 3 games, there will be $2 \cdot 2 \cdot 2=2^3$ possible outcomes, similar to flipping a coin – Vasili Apr 10 '18 at 15:00
  • how do i get a list of the outcomes. How do i get to see the 8 different brackets possible? – jeff Apr 10 '18 at 15:01
  • you can do a tree or a graph of outcomes – Vasili Apr 10 '18 at 15:05
  • if i have a 8 or more team bracket, the amount of possibilities is up in the 10's of thousands, if there a code that can help show all the possible brackets? – jeff Apr 10 '18 at 15:07

2 Answers2

0

For the first round if you have $n$ teams, then you have $\frac{n!}{2^{\frac{n}{2}}(\frac{n}{2})!}$ ways to form all of the pairs. Then from each of those pairs you choose one winner, hence $\frac{n}{2}$ teams are left, for which you can use the argument again. Those $\frac{n}{2}$ teams are chosen in $2^{\text{#of pairs}}$ ways.

Note1: You can use this argument only for $n$ which are powers of $2$.

Note2: You can find a proof of this formula here: Number of possible pairs

asdf
  • 4,587
  • Thank you. how do you do the process manually is what i'm trying to learn. if there a code or a way to do this on excel? – jeff Apr 10 '18 at 14:58
  • I can't imagine doing this with Excel. You could do it in python or any other general purpose programming language. – saulspatz Apr 10 '18 at 15:09
  • I'm am not a coder so i dont really know how to do it. I once asked someone on here to help me create all the combinations of a roster. I had 5 nba players listed on a point scale of 1-5, i had 5 different people i could play. so there were 25 people in 5 separate categories labeled 1-5. to create my roster, i could only use 1 player from each group and could not go over 15 points possible. the man who helped me sent me an excel file of all the combinations. i use it all the time. If anyone knows how to code and help create all the possible bracket combinations, that would be beyond helpful – jeff Apr 10 '18 at 15:15
0

You can do it manually by an iterative process. Once you work it out for $n$ teams for some particular value of $n$ that is of interest to you, you could (with some effort) make a spreadsheet in which each way to bracket the teams occurs in a different row of the spreadsheet.

For a manual process, number the teams from $1$ to $n.$

If $n$ is odd, then one of the teams will be left out of the first round; so already we can partition the set of all possible brackets into $n$ subsets, no two of which ever contain the same bracket. Then, for each choice of which team is left out of the first round, we take the lowest-numbered team from among the other teams, make a list of all the possible ways to pair that team with one of the remaining unassigned teams. So now you have a partial bracket that specifies just one singleton team and one pair. For each of the partial brackets found so far, take the lowest-numbered team not yet included in the bracket, and find all the ways to pair it with one of the remaining unassigned teams. Each of those pairings generates yet another partial bracket from the one you generated it from.

As an example of how the process might have worked so far, suppose you started with $11$ teams. In the first step, then, you have $11$ partial brackets each naming one of the teams as the team left out. For each of those brackets, you have only one lowest-numbered unassigned team, but you have $9$ remaining teams with which to pair it. After you have written out all these possible pairings based on each of your original $11$ partial brackets, you have $11\cdot 9 = 99$ partial brackets. In each of those you have just one lowest-numbered unassigned team, but you have $7$ remaining teams with which to pair it, so after making the second pair in every possible way you have $99\cdot 7 = 693$ partial brackets.

Now as long as you have unpaired teams in the partial brackets, you keep on making lists of possible pairings involving the lowest-numbered team not yet assigned. Each time you do this, each of your partial brackets gets replaced by a (usually larger) set of partial brackets that contain one more pair than the bracket they replaced. Eventually there are only two unpaired teams left and there is only one way to pair them.

So starting with $11$ teams, you end up with $11\cdot9\cdot7\cdot5\cdot3\cdot1 = 10395$ partial brackets.

If $n$ is even, then you skip the step where you choose one team to leave out of the first round. You select the lowest-numbered team not yet assigned (which is team $1$ at this point) and find all the ways to pair it with another team, then in each of those partial brackets you take the lowest-numbered team not yet assigned, etc. For example, for $n = 10$ you have $9$ pairings with team $1,$ and each of those gives rise to $7$ pairings for the next pair of teams, and you end up with $9\cdot7\cdot5\cdot3\cdot1 = 945$ partial brackets.

But at this point you only have the first round of the tournament. Now you take each pair or unpaired team and number these entities from $1$ to $\lceil n/2\rceil.$ That is, if you started with $n=11,$ the first round consists of $5$ pairs plus an unpaired team, so $6$ entities to be numbered from $1$ to $6$; but if $n=10$ then the first round has just $5$ pairs to be numbered from $1$ to $5.$

Now for each partial bracket representing the first round, you work out all the ways to pair up the $\lceil n/2\rceil$ entities of that partial bracket, using the same algorithm you used to pair up teams for the first round. Essentially, for each possible first round you bracket the teams that survive the first round.

For example, if you started with $11$ teams, you have (as before) $10395$ partial brackets showing just the pairings for the first round; since $6$ teams go on to the second round, each of the $10395$ first-round partial brackets generates $5\cdot3\cdot1 = 15$ second-round partial brackets; so now you have a total of $10395 \cdot 15 = 155925$ partial brackets showing the first two rounds.

Repeat round by round until you do a round with just one winner. For example, for $n = 11,$ the $6$ teams that enter the second round leave $3$ teams for the third round, which can be paired in $3\times1$ different ways, leaving one pair for the final round. So altogether you end up with $155925 \cdot 3 = 467775$ brackets for $11$ teams.

I hope you don't mind using a lot of rows in your spreadsheet! I also don't envy you the effort of setting them all up. If the number of teams you're interested in is larger than $8,$ it might be worth the effort to learn enough about how your favorite brand of spreadsheet is stored in a file and learn enough programming in order to automate the process that generates all the rows.

I should point out that the procedure above might include brackets that you would find unsuitable; for example, there is nothing to prevent a team from going through two consecutive rounds without having to play. So you should think about any restrictions of that kind and prevent violations of them; for example, when choosing which team to leave unpaired in a given round, do not list any teams for which this would violate your rules for a "good" bracket. This can reduce the total number of brackets somewhat.

David K
  • 98,388