¿De cuántas maneras se puede construir un equipo de fútbol?

Question

Estoy leyendo un libro sobre la historia del fútbol. Hay varias formas de posicionar un equipo, por ejemplo, cuatro defensas, cuatro centrocampistas y dos delanteros es el común 4-4-2. ¿De cuántas maneras se puede construir un equipo, dado que hay 10 jugadores que se mueven porque el portero está siempre en la misma posición?

Hice algunos esquemas:

10
1-9
1-1-8
1-1-1-7
1-1-1-1-6
1-1-1-1-1-5
1-1-1-1-1-1-4
1-1 1-1-1-1-1-3
1-1-1-1-1-1-1-1-2
1-1-1-1-1-1-1-1-1-1

1-2-7
1-2-1-6
1-2-1-1-5
1-2-1-1-1-4
1-2-1-1-1-1-3
1-2-1-1-1-1-1-2
1-21-1-1-1-1-1-1

1-3-6
1-3-1-5

Entonces pensé en otro esquema, uno que agrupara todas las combinaciones posibles de diagramas a partir del número de líneas que están dispuestas los jugadores en la cancha.

L1 10
L2 1-9,9-1,2-8,8-2,3-7,7-3,6-4,4-6,5-5
L3 

1-1-8,1-8-1,8-1-1,1-2-7,1-7-2, 2-7-1,2-1-7,7-2-1, 7-1-2,1-3-6,1-6-3 .....

No encuentro la fórmula para traducir esto, si es que es correcta.

Buscando una respuesta encontré este sitio. ¿Podría guiarme a un libro o artículo para resolver mi problema?

Answer 1

Resulta que hay una simple reformulación del problema que facilita el recuento. En lugar de escribir una lista de números como (3,5,2) que sumen 10, puedes escribir 10 objetos y colocar separadores que separen los 10 objetos en grupos:

* * *|* * * * *|* *

---

Ejercicio: convéncete de lo siguiente:

• dada cualquier lista de números que sumen 10, se puede dibujar un diagrama correspondiente como el anterior
• dado cualquier diagrama como el anterior, puedes encontrar una lista correspondiente de números que sumen 10
• Si tienes una lista de números, la conviertes en un diagrama y luego la vuelves a convertir en una lista, obtienes tu lista original
• Si tienes un diagrama, lo conviertes en una lista y luego lo vuelves a convertir en un diagrama, obtienes el diagrama original

---

Hay una manera fácil de contar cuántos diagramas se pueden dibujar: hay 9 lugares donde podemos poner un divisor, y para cada lugar, tenemos la opción de poner un divisor allí o no. Por lo tanto, hay $2^9 = 512$ posibles opciones.

Este tipo de diagrama se llama "estrellas y barras", y hay una serie de tipos de problemas que pueden resolverse encontrando una forma de convertir de ida y vuelta el problema que se quiere resolver en diagramas como el anterior.

---

Si queremos contar específicamente el número de listas que tienen un número determinado de entradas, podemos hacer algo similar. Por ejemplo, si queremos que haya exactamente tres puestos (cada uno con al menos una persona), entonces queremos contar el número de formas de insertar dos separadores en una lista de 10 objetos.

Una vez más, convénzase de que puede pasar de las listas a los diagramas. A veces puede ser difícil acertar con estos argumentos.

Si queremos que haya $k$ posiciones, entonces queremos colocar $k-1$ divisores en los 9 lugares posibles, y así hay $\binom{9}{k-1}$ opciones.

Si no has visto coeficientes binomiales (también conocido como combinaciones) antes, esto es igual a

$$ \binom{n}{r} = \frac{n!}{r! (n-r)!} $$

donde $s!$ significa el factorial de $s$ Es decir, que..,

$$ s! = 1 \cdot 2 \cdot \ldots \cdot s $$

(y $0! = 1$ )

Answer 2

Piénsalo así, tienes 10 jugadores que quieres repartir entre 3 posiciones, donde una posición puede tener 0 jugadores. Imagínalos en una línea, para dividirlos en 3 grupos, sacas algunos jugadores para el primer grupo, los separas de la línea, y sacas algunos jugadores para el segundo grupo, y el número restante de jugadores será tu tercer grupo. También podemos imaginar que la separación consiste en poner barreras entre los jugadores de la fila. La pregunta ahora es, ¿cuántas formas hay de insertar las barreras? Considera de nuevo la línea, sólo que esta vez con 12 posiciones: 10 jugadores y 2 barreras. Si simplemente averiguamos dónde poner las barreras, colocamos a los 10 jugadores en las posiciones restantes, y ya tenemos nuestra división. Así, el número total de formas de hacer esto es 12 elige 2, o en notación matemática, $\binom{12}{2} = \dfrac{12!}{10!2!} = 66$ .

Este tipo de problema es un estándar en una rama de las matemáticas llamada Combinatoria. Se le conoce clásicamente como Estrellas y Barras. Puedes leer la página de Wikipedia para más información. http://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29 Para este problema en particular utilizamos el teorema 2 de esa página.

Answer 3

Puedes utilizar una función generadora para resolver esta cuestión: $$(1+x+x^{2}+x^{3}+...+x^{10})(1+x^{2}+x^{4}+...+x^{10})(1+x^{3}+x^{6}+x^{9})(1+x^{4}+x^{8})(1+x^{5}+x^{10})(1+x^{6})(1+x^{7})(1+x^{8})(1+x^{9})(1+x^{10})$$

Expandir el polinomio anterior y el coeficiente de $x^{10}$ es la respuesta.

Código de Mathematica:

$$\text{Coefficient}\left[\text{Product}\left[\text{Sum}\left[x^{i*k},\left\{i,0,\text{Floor}\left[\frac{10}{k}\right]\right\}\right],\{k,1,10\}\right],x,10\right]$$

La respuesta es 42.

Para más información, consulte Conferencias sobre particiones de números enteros y _Particiones enteras_ (Wikipedia).

Answer 4

Para variar, he aquí otro enfoque.

Tu planteamiento inicial parece que te has decantado por la siguiente forma de enumerar todas las formas de hacer una lista de enteros positivos que sumen 10:

• Escribe todas las listas que empiecen por 1 seguidas de una lista que sume 9
• Escribe todas las listas que empiecen por 2 seguidas de una lista que sume 8
• ...

donde se repite el mismo enfoque para escribir todas las listas que suman 9, y así sucesivamente.

Si $f(n)$ es el número de listas que se suman a $n$ Entonces su enfoque sugiere

$$ f(n) = f(n-1) + f(n-2) + \ldots + f(1) + 1 $$

Podemos simplificar esta recurrencia comparando $f(k)$ con $f(k+1)$ : comparten la mayoría de los términos, por lo que si los restamos, la mayoría se anula:

$$ f(k+1) - f(k) = f(k) $$

y por lo tanto

$$ f(k+1) = 2 f(k) $$

Esta recurrencia es muy fácil de resolver: sólo estamos duplicando $f(k)$ cada vez que pasamos al siguiente valor de $k$ . Porque $f(1) = 1$ Por lo tanto, concluimos que $f(n) = 2^{n-1}$ .

Answer 5

Se busca el número de composiciones de 10, esto es $2^{10 - 1} = 512$ .

La prueba de este hecho es similar a la de las estrellas y las barras: Para dividir $n$ en $k$ piezas no vacías es colocar $n$ estrellas, y colocar separadores (barras) en $k - 1$ de la $n - 1$ posiciones entre las estrellas, es decir $\binom{n - 1}{k - 1}$ formas. Sumando sobre todos los números posibles de divisiones es: $$ \sum_{1 \le k \le n} \binom{n - 1}{k - 1} = \sum_{0 \le k \le n - 1} \binom{n - 1}{k} = 2^{n - 1} $$