7 votos

Cuántos arreglos posibles para un torneo round robin?

Cuántos arreglos son posibles para un torneo round robin más de un número par de jugadores de $n$?

Un torneo round robin es una competencia donde $n = 2k$ de los jugadores juegan uno al otro una vez en una partida heads-up (como la fase de grupos de una Copa Mundial de la FIFA). Para ello, hay $n-1$ rondas de con $\frac{n}{2}$ juegos en cada ronda. Para un arreglo de un torneo, vamos a decir que los partidos en el seno de cada ronda son desordenadas, pero las rondas en el torneo están ordenados. Para $n$ a los jugadores, ¿cuántos arreglos posibles de que el torneo puede haber?

...

No sé si una declaración formal es necesaria, pero bueno ...

Deje $P = \{ p_1, \ldots, p_n \}$ ser un conjunto de $n$ jugadores. Deje $R$ denotar una ronda que consiste en un conjunto de pares de $(p_i,p_j)$ (que denota un partido), de tal manera que $0<i<j\leq n$, y de tal manera que cada jugador en $P$ se menciona, precisamente, de vez en $R$. Deje $T$ ser un torneo que consta de una tupla de $n-1$ válido rondas $(R_1, \ldots, R_{n-1})$, de tal manera que todas las rondas en $T$ son pares distintos (no de la ronda de acciones de un partido).

Cuántos válido construcciones de $T$ están allí para $n$ entrada de los jugadores?

La respuesta para 2 jugadores es trivialmente 1. La respuesta para 4 jugadores es de 6. Creo que la respuesta para 6 jugadores a 320. Pero, ¿cómo puede ser resuelto en el caso general?

6voto

David Moews Puntos 11543

Esto es casi la definición de un "$1$-factorización de $K_{2k}$", excepto que un $1$-factorización tiene un desordenado conjunto de matchings en lugar de una secuencia de rondas. Desde allí se $2k-1$ rondas, esto significa que no se $(2k-1)!$ veces como muchos torneos, de acuerdo a la definición anterior, ya que hay $1$-factorizations.

El recuento $1$-factorizations de $K_{2k}$ parece ser un nontrival problema; consulte la Enciclopedia de las Matemáticas de la entrada. El número de $1$-factorizations de $K_{2k}$ es OEIS secuencia A000438. También, vea este papel (también aquí) para un recuento de la $k=7$ de los casos.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X