What is the probability of this exact same Champions League draw?

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),(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.

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.

@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.