El número de extracciones permitidas puede calcularse mediante la técnica de polinomios de rook . El polinomio de la torre de un conjunto finito $D\subset {\bf Z}\times {\bf Z}$ es el polinomio $$r_D(x)=\sum_{k=0}^\infty r_kx^k$$ donde $r_k$ es el número de formas que puede elegir $k$ elementos de $D$ de manera que no haya dos de los $k$ los elementos están en la misma fila o en la misma columna. (Es una suma finita, ya que $D$ es finito. También, $r_0=1$ y $r_1$ es igual al número de elementos en $D$ .)
Queremos contar el número de permutaciones $\sigma$ en ocho objetos que satisfacen las siguientes restricciones: $$\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$$ Aquí $\sigma(i)$ denota el equipo que el $i$ El ganador del grupo se enfrentará en el sorteo dado por la permutación $\sigma$ . El requisito $\sigma(3)\neq 4$ Por ejemplo, el Málaga no puede quedar empatado con el Real Madrid.
El número que nos interesa es el coeficiente $r_8$ del polinomio de la torre del conjunto de pares $(i,j)$ donde $\sigma(i)=j$ no está prohibido por las reglas del sorteo. Esto es difícil de calcular directamente, pero existe una técnica estándar para calcular el polinomio de la torre del conjunto de prohibido y utilizando el principio de inclusión-exclusión.
Dejemos que $D$ sea dada por $$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)\}$$ Primero descomponemos $D=D_1\cup D_2\cup D_3$ , donde $$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 hay dos elementos de diferentes $D_j$ están en la misma fila o en la misma columna, y por lo tanto el polinomio de torre de $D$ factores como $$r_D(x)=r_{D_1}(x)\cdot r_{D_2}(x)\cdot r_{D_3}(x)$$ Los dos primeros factores son triviales, $$r_{D_1}(x)=1+x, \qquad r_{D_2}(x)=1+3x+x^2$$ Para el tercer factor, tenemos que trabajar un poco más. La técnica consiste en elegir uno de los elementos de $D_3$ y dividir los conjuntos de $k$ en la definición de $r_k$ en dos grupos dependiendo de si los conjuntos contienen el elemento elegido o no. Haciendo esto dos veces, pude encontrar $r_{D_3}$ .
Primero, elegí el elemento $(7,4)$ . El polinomio de la torre $r_{D_3}(x)$ se simplifica como $$r_{D_3}(x)=r_{E_3}(x)+x\cdot r_{F_3}(x),$$ donde $E_3$ se obtiene de $D_3$ eliminando sólo el elemento $(7,4)$ y $F_3$ se obtiene de $D_3$ eliminando todos los elementos de la misma fila y la misma columna que el elemento $(7,4)$ . El conjunto $F_3$ es lo suficientemente pequeño como para que los coeficientes de su polinomio de la torre se puedan encontrar por inspección directa, y obtenemos $$r_{F_3}(x)=1+5x+6x^2+x^3$$ Para encontrar el polinomio de la torre del conjunto $E_3$ He utilizado la misma técnica una vez más, esta vez con el elemento $(3,6)$ . Después de inspeccionar las distintas partes, obtuve $$r_{E_3}(x)=(1+5x+6x^2+x^3)(1+3x+x^2)+x\cdot(1+x)^2(1+2x)$$ Juntando las piezas, encontramos ahora $$r_D(x)=1+14x+75x^2+200x^3+286x^4+220x^5+87x^6+16x^7+x^8$$ Por último, volvemos a la cuestión del cálculo del número de sorteos permitidos. Es igual al número de formas en que podemos elegir ocho elementos de $\{1,\dots,8\}\times\{1,\dots,8\}$ tal que no hay dos elementos en la misma fila o columna, y ningún elemento del conjunto $D$ es elegido. Por el principio de inclusión-exclusión, este número es igual a $$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$$
Editar :
Siguiendo un comentario de Marc van Leeuwen, añadí restricciones sobre el equipo con el que se podía enfrentar el Oporto, y calculé en cuántos de los 5463 empates permitidos se enfrentarían a los diferentes equipos. El resultado fue:
Oporto - Schalke 04 en $636$ de los sorteos,
Oporto - Málaga en $1036$ de los sorteos,
Oporto - Borussia Dortmund en $676$ de los sorteos,
Oporto - Juventus en $729$ de los sorteos,
Oporto - Bayern de Múnich en $676$ de los sorteos,
Oporto - Barcelona en $997$ de los sorteos,
Oporto - Manchester United en $713$ de los sorteos.
Obsérvese que los equipos españoles tienen menos rivales admisibles que los demás equipos y, por tanto, serían más probables como rivales del Oporto si todos los empates admisibles tuvieran la misma probabilidad.
6 votos
Grupo F - Valencia (GER) no es un equipo alemán, es español.
1 votos
Tal vez habría que aclarar también que un equipo jugó exactamente contra uno de los otros equipos en la fase de grupos, es decir, el que tiene la misma letra de grupo, y que "ser cabeza de serie" significa que ninguno de los cabezas de serie jugará contra los demás (y en este caso, dado que hay el mismo número de no cabezas de serie, tampoco ninguno de los no cabezas de serie jugará contra los demás). También hay que suponer que el sorteo se selecciona uniformemente entre todos los sorteos admisibles.
1 votos
Tenga en cuenta también que es probable que este hilo sea enlazado por algún sitio de alto nivel tarde o temprano :-)
0 votos
@ulead86 corrigió Valencia como España. gracias.
2 votos
Se puede obtener una visión limitada de las modalidades del sorteo aquí .
1 votos
He desenterrado la normativa para la Liga de Campeones de la UEFA 2012-13; el reglamento de este sorteo se encuentra en el punto 7.09 de la página 12; lamentablemente sólo especifica que "la administración de la UEFA garantiza" que las restricciones que usted enumeró se cumplen, pero no cómo esto está hecho.