Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

As you can see here, there has been a strange coincidence with the UEFA Champions League draw. The real draw which took place today, ended up being exactly the same as the rehearsal draw which took place yesterday.

Considering the following rules, what is the probability of this?

Group stage winners:

  • Group A - Paris St. Germain (FRA)
  • Group B - Schalke 04 (GER)
  • Group C - Malaga (ESP)
  • Group D - Borussia Dortmund (GER)
  • Group E - Juventus (ITA)
  • Group F - Bayern Munich (GER)
  • Group G - Barcelona (ESP)
  • Group H - Manchester United (ENG)

Group stage runner-ups:

  • Group A - Porto (POR)
  • Group B - Arsenal (ENG)
  • Group C - AC Milan (ITA)
  • Group D - Real Madrid (ESP)
  • Group E - Shakhtar Donetsk (UKR)
  • Group F - Valencia (ESP)
  • Group G - Celtic (SCO)
  • Group H - Galatasaray (TUR)

Winners from the group stage were seeded but they could not be drawn against a team who they played in the group stage, or another team from their association.

share|improve this question
6  
Group F - Valencia (GER) it's not a german team, it's spanish. –  ulead86 Dec 20 '12 at 13:34
1  
It should perhaps also be clarified that a team played exactly one of the other teams in the group stage, namely the one with the same group letter, and that "being seeded" means that none of the seeds will play each other (and in this case since there is an equal number of non-seeds also none of the non-seeds will play each other). Also it should presumably be assumed that the draw is selected uniformly among all admissible draws. –  joriki Dec 20 '12 at 13:44
1  
Also note that this thread is likely to be linked by some high-profile site sooner or later :-) –  joriki Dec 20 '12 at 13:46
2  
Some limited insight into the modalities of the draw might be gained here. –  joriki Dec 20 '12 at 14:17
1  
I dug up the regulations for the 2012–13 UEFA Champions League; the regulations for this draw are in item 7.09 on page 12; unfortunately they only specify that "the UEFA administration ensures" that the constraints that you listed are fulfilled, but not how this is done. –  joriki Dec 20 '12 at 14:32
show 1 more comment

6 Answers 6

up vote 8 down vote accepted

The number of permissible draws can be computed by the technique of rook polynomials. The rook polynomial of a finite set $D\subset {\bf Z}\times {\bf Z}$ is the polynomial $$r_D(x)=\sum_{k=0}^\infty r_kx^k$$ where $r_k$ is the number of ways you can choose $k$ elements from $D$ such that no two of the $k$ elements are in the same row or the same column. (It is a finite sum, since $D$ is finite. Also, $r_0=1$, and $r_1$ is equal to the number of elements in $D$.)

We want to count the number of permutations $\sigma$ on eight objects which satisfy the following restraints: $$\sigma(i)\neq i, \qquad i=1,\dots,8$$ $$\sigma(3)\neq 4,\quad \sigma(3)\neq 6,\quad \sigma(5)\neq 3,\quad \sigma(7)\neq 4, \quad \sigma(7)\neq 6,\quad \sigma(8)\neq 2$$ Here $\sigma(i)$ denotes the team that the $i$th group winner will meet in the draw given by the permutation $\sigma$. The requirement $\sigma(3)\neq 4$, for instance, means that Malaga is not allowed to be drawn against Real Madrid.

The number we are interested in is the coefficient $r_8$ of the rook polynomial of the set of pairs $(i,j)$ where $\sigma(i)=j$ is not prohibited by the rules of the draw. This is difficult to compute directly, but there is a standard technique of computing the rook polynomial of the set of forbidden pairs, and then using the inclusion-exclusion principle.

Let $D$ be given by $$D=\{(1,1),(2,2),(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(3,4),(3,6),(5,3),(7,4),(7,6),(8,2)\}$$ We first decompose $D=D_1\cup D_2\cup D_3$, where $$D_1=\{(1,1)\},\qquad D_2=\{(2,2),(8,8),(8,2)\},$$ $$D_3=\{(3,3),(4,4),(5,5),(6,6),(7,7),(8,8),(3,4),(3,6),(5,3),(7,4),(7,6)\}$$ No two elements from different $D_j$'s are in the same row or the same column, and hence the rook polynomial of $D$ factors as $$r_D(x)=r_{D_1}(x)\cdot r_{D_2}(x)\cdot r_{D_3}(x)$$ The first two of these factors are trivial to find, $$r_{D_1}(x)=1+x, \qquad r_{D_2}(x)=1+3x+x^2$$ For the third factor, we need to work a little more. The technique is to pick one of the elements in $D_3$, and to divide the sets of $k$ elements in the definition of $r_k$ into two groups depending on whether the sets contain the picked element or not. By doing this twice, I was able to find $r_{D_3}$.

First, I picked the element $(7,4)$. The rook polynomial $r_{D_3}(x)$ simplifies as $$r_{D_3}(x)=r_{E_3}(x)+x\cdot r_{F_3}(x),$$ where $E_3$ is obtained from $D_3$ by removing just the element $(7,4)$, and $F_3$ is obtained from $D_3$ by removing all elements in the same row and the same column as the element $(7,4)$. The set $F_3$ is small enough so that the coefficients of its rook polynomial can be found by direct inspection, and we get $$r_{F_3}(x)=1+5x+6x^2+x^3$$ To find the rook polynomial of the set $E_3$, I used the same technique once more, this time with the element $(3,6)$. After inspecting the various parts, I got $$r_{E_3}(x)=(1+5x+6x^2+x^3)(1+3x+x^2)+x\cdot(1+x)^2(1+2x)$$ Putting the pieces together, we now find $$r_D(x)=1+14x+75x^2+200x^3+286x^4+220x^5+87x^6+16x^7+x^8$$ Finally, we return to the question of computing the number of permissible draws. It is equal to the number of ways we can choose eight elements from $\{1,\dots,8\}\times\{1,\dots,8\}$ such that no two elements lie in the same row or column, and no element from the set $D$ is picked. By the inclusion-exclusion principle, this number is equal to $$N=\sum_{k=0}^8 (-1)^k(8-k)!\cdot r_k=40320-5040\cdot 14+720\cdot 75-120\cdot 200+24\cdot 276-6\cdot 220+2\cdot 87-1\cdot 16+1\cdot 1=5463$$

Edit:

Following up on a comment by Marc van Leeuwen, I added constraints on which team Porto was allowed to meet, and computed in how many of the 5463 permissible draws they would meet the different teams. The result was:

Porto - Schalke 04 in $636$ of the draws,

Porto - Malaga in $1036$ of the draws,

Porto - Borussia Dortmund in $676$ of the draws,

Porto - Juventus in $729$ of the draws,

Porto - Bayern Munich in $676$ of the draws,

Porto - Barcelona in $997$ of the draws,

Porto - Manchester United in $713$ of the draws.

Note that the Spanish teams have fewer permissible opponents than the other teams, and hence would be more likely as an opponent for Porto if all permissible draws were given the same probability.

share|improve this answer
    
That's what I'm looking for. –  erkanyildiz Dec 24 '12 at 13:00
add comment

If it weren't for the constraint on the association, this would be the number of derangements of 8 items, which is $14833$. It's hard to take the association constraints into account systematically, so I wrote code that does it. The result is $5463$ possible matchings, so if one of them was picked uniformly, the chance was $1$ in $5463$.

However, it seems likely that this isn't how it was done, since the draw is a public event (as witnessed by the "rehearsal"), and picking a draw uniformly by computer wouldn't be fun, and it's not obvious which publicly displayable drawing scheme would lead to a uniform distribution over all matchings.

Thus, to answer the question precisely, we'd need to know how both draws were carried out. However, the probability $1$ in $5463$ calculated on the assumption of a uniform distribution is likely to be a good approximation of the actual probability.

share|improve this answer
    
thanks for the answer. but can't we exactly calculate it, instead of counting possible matchings? –  erkanyildiz Dec 20 '12 at 14:27
1  
@erkanyildiz: I don't understand that distinction. I calculated the probability exactly, under the assumption of a uniform distribution, by counting the possible matchings. We can't do any better than that unless we find out how exactly the draws were carried out. –  joriki Dec 20 '12 at 14:30
    
I'm sorry. I've just noticed the word "exactly" is a little bit confusing there. I know that the number you have found is the exact answer. My comment was about the method. You've said "It's hard to take the association constraints into account systematically" and what I want is this systematical method. For example, What if Juventus is not an Italian club, but a French one. We have to count all the possible matchings again? –  erkanyildiz Dec 20 '12 at 14:44
add comment

@erkanyildiz It depends what you mean by "systematic method". Computing the probability is the same as computing the number of possible perfect matchings in the bipartite graph where on one side you have the 8 winners of the groups, on the other side the 8 seconds, and you have an edge between every allowed pair. Computing this is the same as computing the permanent of the $8\times 8$ adjacency matrix (entry $(i,j)$ equals $1$ if the two teams can play together, $0$ otherwise). Computing the permanent can be done by Ryser's formula, which can be computed in time $O(n2^n)$ ($n=8$ in this case). Note that computing the permanent of a matrix (and indeed computing the number of perfect matchings) is #P-hard.

share|improve this answer
add comment

The number of all different draws is really 5463 if we don't care about sequence of teams in draw. Checked this by program. To be absolute sure - checked in cycle all 8^16 variants. Not permissible draws were excluded, permissible 220268160=5463*40320 were put to array (in 5463 rows and counter for each row - got 40320 in each row ). 40320=8*7*6*5*4*3*2 - number of variations for each 5463 draw depending on sequence of draw. Then put this array of 5463 rows to txt - to visually check that all draws are correct.

30 min my laptop were busy with this task))) source code and generated txt (200Kb) http://letitbit.net/download/03893.0272e41c19e54924caf07c062809/CL_draw.7z.html

Per Manne did great job writing this probability in math, and his statistic for Porto is also correct, my generated txt that was converted to xls http://letitbit.net/download/28422.2cbcde9acc7e85ec8bd87c718f25/draw.7z.html (125KB) could be used to easy count such probability for other teams (excel filter):

for example:

Arsenal - Barcelona 1161/5463; Arsenal - Bayern Munich 774/5463; Arsenal - Borussia 774/5463; Arsenal - Juventus 827/5463; Arsenal - Malaga 1214/5463; Arsenal - Paris St. Germain 713/5463;

AC Milan - Borussia 849/5463; AC Milan - Barcelona 1267/5463; AC Milan - Bayern Munich 849/5463; AC Milan - Man United 905/5463; AC Milan - Paris St. Germain 791/5463; AC Milan - Shalke 802/5463;

Real Madrid - Juventus 1189/5463; Real Madrid - Bayern Munich 1068/5463; Real Madrid - Man United 1175/5463; Real Madrid - Paris St. Germain 1005/5463; Real Madrid - Shalke 1026/5463;

Shakhtar - Barcelona 1022/5463; Shakhtar - Bayern Munich 689/5463; Shakhtar - Borussia 689/5463; Shakhtar - Malaga 1055/5463; Shakhtar - Man United 724/5463; Shakhtar - Paris St. Germain 638/5463; Shakhtar - Shalke 646/5463;

Valencia - Borussia 1068/5463; Valencia - Juventus 1189/5463; Valencia - Man United 1175/5463; Valencia - Paris St. Germain 1005/5463; Valencia - Shalke 1026/5463;

and so on

share|improve this answer
    
@NomPrenom " Indeed, all draws do not have equal probability. For the one that occurred, the probability is roughly 1/5515." - how you counted that? As for my results of draw modelling by code all 5463 draws has equal probability to happen. –  igor Dec 23 '12 at 19:31
    
@Nom Prenom for every succesful (legal) draw there are 8! =4320 variants it could happen depending on the teams order - yes. I'm just don't sure that your sum of "successive number of possible choices for each opponent" for each of 4320 variant of the particular draw is the probability of that draw. Did you checked that sum of such encounted probabilities of all acceptable draws (5463) is equal to 1? –  igor Dec 24 '12 at 17:40
    
@Nom Prenom Just when I simulated it on PC I took 16 round cycle 1 to 8, after each cycle was filter: the variants when choosen team was inacceptable to draw rules didn't count like it couldn't happened. For Example for existing draw when Milan got not Barcelona and future collision took place the result didn't counted like it coudn't happen - only 1 result was counted when Milan took Barsa. Then each result that satisfied all rules was analyzed and put to array 1..5463 rows and number of such draw variants was calculated. Finally I received 5463 draws each could happen 4320 times. –  igor Dec 24 '12 at 17:50
    
I understand this the next way. During draw could happen 4320*5463 acceptable by rules situations. And every draw should have equal probability to happen. –  igor Dec 24 '12 at 17:55
add comment

Thanks for the very interesting and very elegant method using rook polynomials. As for me, poor computer scientist, I simply generated (by code) all possible draws, and there are indeed 5463 such draws. However, to get the exact probability of each draw, one needs to compute the probability of each team ordering, taking into account the way teams are selected. Indeed, all draws do not have equal probability. For the one that occurred, the probability is roughly 1/5515.

share|improve this answer
    
Cool. Do you have info what the maximum and minimum probabilities are? Also maybe the probability that the drawing "stalls" because no valid opponent is available for the current situation? –  Hagen von Eitzen Dec 23 '12 at 10:01
    
Yes, it can stall very often -- if nothing is done to prevent it -- and of course, these events should never occur in the real draw. This is why UEFA needs to use bowls to only put the teams (given by a computer) that will never lead to a stall. For example, the draw that was selected on Friday selected Galatasaray, then Celtic, Arsenal, Shaktar, Milan, etc. And for Milan, only one choice was possible at this point (Barca) to avoid further stalls. The probability of this particular draw is (8!)x(7x6x5x5x1x2x1x1). –  Nom Prenom Dec 23 '12 at 10:16
    
The minimum probability is roughly 1/6526, the maximum roughly 1/4722. –  Nom Prenom Dec 23 '12 at 10:21
    
@igor: take for example the very specific draw that was selected. As I explained, it has probability 1 divided by 8! (probability to select the order of the teams that arrive second) times 7x6x5x5x1x2x1x1 (successive number of possible choices for each opponent) = (1/40330)x(1/2100). To get the probability of a particular assignment of pairs (but in any order), I computed this kind of value for all orders and summed the results. This gives the numbers I gave. If all draws had equal probability, then they would all have all this particular probability. But 2100 is obviously not equal to 5463. –  Nom Prenom Dec 24 '12 at 10:37
    
@igor: How to explain more? Yes, the total probability I find, summing over all draws, is of course 1 even if all draws don't have the same probability. And it's obvious if you think of what the UEFA process is: it's like a tree where each node has as many children as choices at this stage (a choice depends on the opponents allowed by the rules but also to avoid "deadlocks", e.g., see Milan with a single choice, Barca, even if Paris and MU were still allowed by the rules). The probability of a draw (a leaf) is 1 over the product of the degrees to this leaf. Then, you sum over all permutations. –  Nom Prenom Dec 27 '12 at 13:17
add comment

The draw is organized like this:

One bowl has all runners-up. Then there is eight other bowls for each group winner.

One team is drawn from the runners-up (the reason why they draw them is probably simply pedagogic since they are set to play at home in the first leg).

Then a bowl is filled with a ball from each team not excluded by the rule about same league or group stage group. One ball is then picked.

So this method leaves does not alter the statistical possibility compared to how you have coded it (at least from the little i understand of code). 1 in 5463 should thus be correct also for the live draw.

share|improve this answer
4  
Thank you for the precision about the method, which seems quite plausible. However the claim that the method does not affect the probabilities of outcomes is clearly false. Since the prime factorization of $5463$ is $3^3\times607$, you can only ensure a uniform probability if either some elementary choice involves one out of a multiple of $607$, or if the method includes the possibility to block because of a violation, and start all over again. Neither are true for the method described, though it could conceivably block if a runner-up is left for which the set of admissible opponents is empty. –  Marc van Leeuwen Dec 21 '12 at 13:44
    
There is no possibility of a violation in the way it is done manually, but I might be mnissing your point? Im not good at reading code, but it seems to me that it excludes both the possibility of picking teams that were grouped and teams that share nationality. If Im correct in this, the same rules would apply to the manual draw, since they fill the second bowl only with the teams that are eligable to meet the team they draw from the bowl of runner-ups (and then ofc emptying it before drawing the next team from the R-U's). –  user53858 Dec 21 '12 at 22:13
    
The main point is that in order to ensure equal probability for every legal outcome, it does not suffice that illegal outcomes are excluded and all legal outcomes are possible, as this procedure ensures. For instance Porto could legally face any of the group winners except PSG, but among the legal outcomes the exact $7$ probabilities of these events cannot all be equal: they are numbers of the form $\frac n{5463}$ (@joriki might tell you the values of $n$), and then number $\frac17$ cannot be written in this form. Making these events equally like makes legal outcomes unequally likely –  Marc van Leeuwen Dec 22 '12 at 9:59
    
@MarcvanLeeuwen See my answer for these values of $n$. They vary quite a lot! –  Per Manne Dec 22 '12 at 18:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.