What is the probability of this exact same Champions League draw? 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.
 A: 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.
A: @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. 
A: 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.
A: 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.
