Número de equipos y partidos

Question

Esta pregunta tiene dos partes.

1. Dado n jugadores, ¿cuántos equipos diferentes se pueden crear con al menos uno y como máximo n-1 ¿jugadores?

Por ejemplo, dados los cuatro jugadores A, B, C y D, se pueden crear los siguientes equipos:

A B C D AB AC AD BC BD CD ABC ABD ACD BCD

Creo que este es el conjunto de potencia, con la excepción del propio conjunto y el conjunto vacío. Por lo tanto, la respuesta debería ser $2^n-2$ .

2. ¿Cuántos partidos diferentes se pueden crear entre los equipos a partir de 1) de forma que ningún jugador se enfrente a sí mismo y cada equipo se enfrente a uno solo?

Por ejemplo, eso significa que el equipo A no puede jugar contra el equipo ACD, y AC no puede jugar contra AD, ya que A está en ambos equipos. Además, el partido A contra B es el mismo partido que B contra A, ya que los equipos se enfrentan sólo una vez. La fuerza bruta da los siguientes 25 partidos:

                        A A A B
            A A A B B C B B C C
    A B C D B C D C D D C D D D
  A| |*|*|*| | | |*|*|*| | | |*|
  B| | |*|*| |*|*| | |*| | |*| |
  C| | | |*|*| |*| |*| | |*| | |
  D| | | | |*|*| |*| | |*| | | |
A B| | | | | | | | | |*| | | | |
A C| | | | | | | | |*| | | | | |
A D| | | | | | | |*| | | | | | |

¿Puede alguien ayudarme a determinar el número de tales partidos en el caso general?

Answer 1

$2^n-2$ es correcto para la primera pregunta. Pasemos a la segunda pregunta.

En primer lugar, supongamos que vamos a elegir un equipo "local" y otro "visitante". (Esto duplicará el número de partidos. Como no se distingue entre los dos equipos en un partido, lo corregiremos dividiendo por dos al final).

Tenemos tres opciones para cada jugador: ponerlo en el equipo local, ponerlo en el equipo visitante, o ninguno. Así que, como primera aproximación, hay $3^n$ partidos. Pero esto incluye los partidos en los que uno o ambos equipos no tienen jugadores. Hay $2^n$ partidos sin nadie en el equipo local, $2^n$ partidos sin nadie en el equipo visitante, y $1^n=1$ partido sin nadie en ninguno de los dos equipos. Por el principio de entrada y salida (también conocido como principio de inclusión y exclusión) el número de partidos con ambos equipos no vacíos es $3^n-2^n-2^n+1$ que tenemos que dividir por dos para responder a la pregunta original. La respuesta final es $$\frac{3^n-2^{n+1}+1}2.$$

Answer 2

Tienes razón en la primera pregunta; la respuesta es $2^n-2$ .

El número de partidos en la segunda pregunta se puede contar por el número de jugadores totales en el partido.

Si hay $n$ jugadores, entonces el número de partidos con un total de $k$ jugadores, con $2 \leq k \leq n$ es el número de formas de elegir el $k$ jugadores implicados, multiplicado por el número de formas de dividir los equipos, dado el $k$ jugadores. Esto es

$$\binom{n}{k} \left(2^k-2\right)$$

El $2^k-2$ El término proviene del hecho de que los equipos son no vacíos y no de tamaño $k$ (ya que un equipo de tamaño $k$ haría que el otro equipo fuera de tamaño cero).

Esto cuenta dos veces cada posible coincidencia. El número total de coincidencias posibles $M$ para $n$ jugadores, entonces, es

$$M= \frac{1}{2}\displaystyle\sum\limits_{k=2}^{n} \left[\binom{n}{k}\left(2^k-2\right)\right]$$

Esta suma se puede escribir

$$2M = \displaystyle\sum\limits_{k=0}^{n} \left[\binom{n}{k}\left(2^k-2\right)\right] + 1$$

$$2M = \displaystyle\sum\limits_{k=0}^{n} \left[\binom{n}{k}2^k\right] - 2\displaystyle\sum\limits_{k=0}^{n}\binom{n}{k}+1$$

El término de la izquierda es la expansión de $(1+2)^n$ y el término medio es el doble de la suma de una fila del triángulo de Pascal, por lo que obtenemos la bonita forma cerrada de la respuesta final:

$$M = \frac{3^n - 2^{n+1}+1}{2} \qquad \text{possible matches}$$

---

Como comprobación, observe que $n=4$ da su resultado calculado: $25$ .