| 0 |
Subject: Bracket Permutations
Posted by: Boxman
- [25218205] Mon, Mar 20, 2006, 06:29
How many different permutations of an NCAA bracket are there? |
| 1 | The Beezer
Leader
ID: 191202817
Mon, Mar 20, 2006, 06:49
|
According to this guy, it is 2^31 or 2,147,483,648. That's assuming the play-in winner doesn't matter.
|
| 2 | Slowhand
SuperDude
ID: 056744223
Mon, Mar 20, 2006, 10:35
|
I guess that means I've got to do more brackets next year ;-)
|
| 3 | Guru
ID: 330592710
Mon, Mar 20, 2006, 10:43
|
There are 63 games played, each with 2 possible outcomes. Without thinking through this too long, why wouldn't the answer simply be 263?
|
| 4 | beastiemiked
Leader
ID: 03531815
Mon, Mar 20, 2006, 11:02
|
Pretty sure Guru is right.
Number of Brackets = (64)(32)(2*16)(4*8)(8*4)(16*2) = 26 * 25 * 25 * 25 * 25 * 25 = 231 = 2,147,483,648.
I think it should be (64)(32)(16^2)(8^4)(4^8)(2^16) = 2^63
|
| 5 | wolfer
ID: 38502920
Mon, Mar 20, 2006, 20:07
|
Another opinion.
|
| 6 | Smith32
ID: 4325359
Mon, Mar 20, 2006, 20:22
|
I agree with the Guru and offer the following link in support:
http://mathforum.org/library/drmath/view/56223.html
|
| 7 | Slowhand
SuperDude
ID: 056744223
Mon, Mar 20, 2006, 20:32
|
I guess that means I'll have to fill out even MORE brackets
|
| 8 | The Beezer
Leader
ID: 191202817
Mon, Mar 20, 2006, 21:05
|
Note to self: you shouldn't "feel lucky" with math links before 8am on Mondays.
2^63 looks right to me. Here's another way of looking at it.
It's easy to see that for a four team tournament, you have 8 possible outcomes. A 64 team tournament is just 16 different four team tournaments that each feed into 4 four team tournaments, which then feeds into a final 4 team tournament. (We think of it this way anyway with 4 teams vying for a Sweet 16 berth, followed by 4 teams going for a Final Four berth, then of course the championship)
That would be 8^16 or 2^48 outcomes for the 16 initial tournaments, which can be multiplied by 8^4 or 2^12 second level tournaments, which is then multiplied by 1 third level tournament with 8 or 2^3 outcomes. This is (2^48)*(2^12)*(2^3)=2^63.
BTW, I like how the Dr. Math guy goes through and counts in each round to see how many total games are played, instead of just accouting for the fact that every team except one loses 1 game, so there are 63 in a 64 team bracket. Or 217 games in a 218 team bracket, for that matter.
|
| 9 | Salt Bandit
ID: 011542816
Tue, Mar 21, 2006, 00:46
|
Slightly off topic, but a similar question. It may be to complicated to fully answer, but I still think it's an interesting one.
How many brackets would need to be filled out to expect a correct bracket with a certain level of confidence? I'd like to include prior probabilities in the answer (which could be estimated from this data).
For example, if I assume all 4 #1 seeds win in the first round, and leave all other games as 50/50, I could reduce the total brackets I'd need to fill out by a factor of 16 without significantly reducing my confidence level. I could do the same with #2 seeds, and reduce by a total factor of 256, though my confidence level would drop more significantly.
Without looking into it too much right now, this seems similar to an information theory problem (such as in digital communications, reducing the number of bits in a transmission depending on the entropy of the signal). I would expect there to be a statistics/probability approach to the problem also though.
If I have more free time later, I'll look back through my notes and see if I can write an algorithm to solve this problem....
|
| 10 | Sludge
ID: 14411118
Tue, Mar 21, 2006, 01:39
|
A few years back, I actuall wrote a program for Guru's Market Madness game that did the following:
Took Jeff Sagarin's ratings for each team. Based on those ratings, you can compute the estimated probability of team A beating team B. Simulate a few billion tournaments. Long the teams that produced the largest expected net profit, short the teams that produced the smallest expected net profit. One thing I did not implement (don't know exactly why) was a correlation matrix between all the possible selections to help maximize expected net profit, as just selecting like I state above isn't necessarily optimal (or even near-optimal... just guessing).
As to Salt Bandit's question, estimating the probability of a particular bracket is easy. It's just the product of the selected teams a priori probabilities of winning each particular game. The most likely bracket is that which selects each team that is most likely to win in each game. From that point on, figuring out the 2nd, 3rd, 4th, etc. most likely brackets is, I would imagine, a non-trivial problem.
|
| 11 | steve houpt
ID: 451161019
Thu, Mar 23, 2006, 03:26
|
How about ((((8)^2)^2)^2)^2 or 8^16 ??
or ((((2^3)^2)^2)^2)^2 or 2^48 ??
Have not worked the math brain 'hard' in a while.
Four team bracket has 8 possibilities as stated numerous times above. You have 16 four team brackets. 8^16.
Double checking the long way:
Two four team brackets [8 teams] produces 8^2 possibilities [64].
Another two four team brackets produces 8^2 possibilities [64].
Those two brackets [16 teams] have [64^2] possibilities [or 4,096].
Another 16 team bracket would have 4,096 possibilities.
That 32 team bracket would have 4,096^2 possibilities [or 16,777,216].
Another 32 team bracket has 16,777,216 possibilities.
16,777,216^2 = 8^16 = 281,474,976,710,656
Maybe the move to South Carolina fried my brain, or I still have Post Katrina Syndrome, but that's my best guess.
|
| 12 | Guru
ID: 330592710
Thu, Mar 23, 2006, 21:44
|
Wow, an old time Gurupie returns!
There are actually 21 4-team brackets, though. 16 in the first round, followed by 4 regionals, plus the final four.
That's 821, or (23)21, which is the same 263 I came up with above, using a simpler process (63 games, 2 outcomes per game).
|
| 13 | steve houpt
ID: 451161019
Thu, Mar 23, 2006, 22:28
|
Guru - but each 'four team' bracket does not have a chance of meeting every other bracket in the tourney, only other specific four teams brackets as they move up.
That's why I 'kind of' worked it backwards.
Not 100% convinced I'm correct. But my guess is your number would be correct if there was 'reseeding' of the teams after each round. Would open all possibilities up.
i.e. - LSU could not meet Duke until round three.
|
| 14 | Mark L
ID: 172412321
Thu, Mar 23, 2006, 22:47
|
No kidding, I only played Market Madness once but I saw SH as the
"last post" and had to check it out.
Good to see you here, Steve, and hope all's well.
|
| 15 | Sludge
ID: 14411118
Thu, Mar 23, 2006, 23:34
|
Sorry, steve. Guru's correct.
|
| 16 | weykool
ID: 362402022
Fri, Mar 24, 2006, 00:21
|
The answer is 2^63.
You have 63 games and each game has a possibilty of two outcomes.
The other method where you are using multiple 4 team brackets still works.
Lets assume you have 8 teams so you make 2 brackets of 4.
We know that 1 bracket of 4 has 2^3 or 8 possible outcomes.
You take each of those 8 outcomes and multiply it by the 8 outcomes of the 2nd bracket.
8*8=64.
You then have 2 outcomes for the final game for a total of 128 possible outcomes.
(2^3)*(2^3)*2=2^7 (You add exponents when you multiply).
In the 8 team example you have 7 games so 2^7 is your answer.
For 64 teams you have 63 games.
2^63= 18,446,744,073,709,600,000
The figure offered in post #1 is the correct answer for a 32 team bracket.
If you cant follow what I said...then what Guru said.
|
| 17 | weykool
ID: 362402022
Fri, Mar 24, 2006, 00:30
|
Opps....bad formula in my excel sheet.
Take half of the 18 bazilion number.
2^63 = 9,223,372,036,854,780,000
The 18 Bazilion number would be correct if you included the play in game.
|
| 18 | Piccolos @ work
ID: 46262611
Sun, Mar 26, 2006, 12:44
|
You guys missed the playin game!!! Add another huge number to the mix. Here's Yahoo's explanation:
Explanation of Perfect Bracket
|
| 19 | Sludge
ID: 14411118
Sun, Mar 26, 2006, 13:28
|
You guys missed the playin game!!!
Uhh... check the message right above yours. Everyone here is mindful of the play-in game.
|
| 20 | Sludge
ID: 14411118
Sun, Mar 26, 2006, 13:30
|
From the Yahoo story:
Math Forum confirmed our logic and also offered an interesting side note we'll paraphrase for you. If every person on the planet (around 6.5 billion) filled out a bracket, the odds of someone (anyone!) achieving perfection are still infinitesimal. Suddenly keno's not looking like such a bad deal.
Likely that would be assuming blind guessing on every one of the 6.5 billion people's part.
|
| 21 | Wilmer McLean
ID: 142252615
Tue, Mar 28, 2006, 21:37
|
What are the odds that two people will have the same bracket?
|
| 22 | Salt Bandit
ID: 011542816
Tue, Mar 28, 2006, 23:03
|
Re:[21]
Assuming each person fills out the bracket completely randomly (the assumption that was made throughout this thread), I think the odds of 2 specific people having the same bracket is the same as the odds that someone will fill out a bracket correctly. You can consider the 1st person's bracket the "correct" bracket, then calculate the odds that the 2nd person fills out the "correct" bracket.
Of course, most people don't fill out their brackets completely randomly, which would change those odds.
Also, if instead of 2 specific people, you could consider the odds of any 2 people in a larger group filling out the same bracket. Those odds would be different, though I can't remember how to calculate them off the top of my head.
|
| 23 | Sludge
ID: 14411118
Wed, Mar 29, 2006, 01:52
|
Also, if instead of 2 specific people, you could consider the odds of any 2 people in a larger group filling out the same bracket. Those odds would be different, though I can't remember how to calculate them off the top of my head.
It's just 1-P(None of them pick the same bracket). That probability is far easier to compute than trying to compute P(2 or more picking the same bracket) directly.
|
| 24 | MathDunce
ID: 72481512
Thu, Mar 15, 2012, 13:49
|
Ok, I understand 2^63, so maybe I am not a total dunce.
But how to we figure out the permutations of a situation more likely to happen? For instance, how can we find the permutations where the #1s all win in the first round, since they have never lost. I'm pretty certain it doesn't become 2^59, right? Because we still want to account for those 4 teams in the next round.
Is it (2^63)-(2^59)?
What about if we want to advance all the #2s (since they have only lost 4 times, I think)?
Can we use (2^63)-(2^59)-(2^55)?
|
|
|
|
Post a reply to this message: Bracket Permutations
|
|