¿De cuántas maneras se pueden distribuir 70 aviones en 4 pistas?

Question

Estoy haciendo algunos preparativos para un próximo examen, y un poco confundido acerca de este problema:

_"En un aeropuerto, se reparten 70 aterrizajes por hora entre 4 pistas. Cualquier vuelo puede aterrizar en cualquiera de las pistas y cada vuelo aterriza en exactamente una pista. Los controladores controladores de tráfico aéreo sólo están interesados en el número de vuelos en cada pista y no qué vuelos son.

¿De cuántas maneras puede el controlador de tráfico aéreo asignar la entrada de 70 vuelos por hora a las pistas? (Algunas pistas pueden no tener vuelos)"_

A mi entender, en este problema no se permiten las repeticiones, y el orden no importa:

• Las repeticiones no están permitidas ya que una vez que se baja un avión en una pista, no se puede bajar ese avión en otra pista.

• El orden no importa porque como la la pregunta lo dice, "Los controladores de tráfico aéreo controladores sólo se interesan por el número de vuelos en cada pista, no qué vuelos son"

Cuando tenemos repeticiones no permitidas y el orden no importa, utilizamos la fórmula Choose $C(n,r)$ que da como resultado $C(70,4)$

Sin embargo, esto es incorrecto, la solución correcta dice:

El problema es equivalente a encontrar el número total de soluciones de $x1 + x2 + x3 + x4 = 70$ que termina siendo $C(73,3)$ . Utilizando la fórmula $C(r+n-1, n-1)$ que corresponden a situaciones en las que las repeticiones ESTÁN permitidas, y el orden no importa.

¿Qué me falta?

Answer 1

Cuando lo hagas $C(70,4)$ , está seleccionando 4 de 70 posibilidades. Esto hace no corresponden a asignar una pista a cada uno de los 70 aviones (piénsalo: sólo estás seleccionando cuatro de los 70 aviones que llegan... ¿para qué?)

En cambio, lo que hay que hacer es seleccionar una pista, de entre 4 posibilidades, 70 veces (una para cada avión), permitiendo la repetición de pistas (una misma pista puede ser utilizada por más de un avión), y sin importar el orden en que se seleccionen. Se trata de un clásico "problema de combinación con repeticiones", también conocido como problema de estrellas y barras.

Con el fin de hacer $r$ selecciones de $n$ posibles elementos, permitiendo repeticiones ilimitadas y donde el orden de las selecciones no importa (sólo cuántas veces se selecciona cada elemento), la fórmula correcta es $$\binom{n+r-1}{r} = \binom{n+r-1}{n-1}$$ que en este caso (con $n=4$ las pistas de aterrizaje disponibles, y $r=70$ , el número de veces que hay que seleccionar una pista) arroja la respuesta proporcionada, $\binom{73}{3}$ .

Answer 2

La forma más sencilla de verlo es como dice la pista, que $x_i$ los aviones aterrizan en la pista $i$ entonces se buscan soluciones enteras no negativas para $$x_1 + x_2 + x_3 +x_4 =70$$

Que puede verse gráficamente como el número de formas de atravesar un $3\times 70$ cuadrícula de una esquina a otra haciendo sólo movimientos hacia la derecha y hacia arriba.

El número total de movimientos es $73$ de los cuales 3 tienen que estar arriba, o, de forma equivalente $70$ tienen que ser correctas, por lo que el número total de formas es $$\binom{73}{3} = \binom{73}{70}$$ Otra forma es imaginar una cuadrícula bidimensional con 70 columnas y 3 filas. En esta $3\times 70$ cada fila representa una pista de aterrizaje y cada columna representa un plano. Así, por ejemplo, una pista TRUE o $1$ en un punto de la red $a_{ij}$ dice que el avión $j$ aterrizó en el $i$ de la pista. Cada columna contendrá un TRUE $1$ y tres falsos o $0$ como avión $j$ puede aterrizar en sólo uno de los $i=4$ cuatro pistas. Obsérvese que la reordenación de las filas o las columnas no cambiaría estas construcciones.

Si $X$ es el conjunto de todas las matrices construidas con la regla anterior, y $P(X)$ es el conjunto que se obtiene permutando las columnas de forma que todas las $1's$ en una fila ocurren juntos, entonces es fácil ver que el mapeo $f:S\rightarrow P(S)$ es biyectiva. La cardinalidad de $P(S)$ se conoce desde arriba, es el número de formas de atravesar una cuadrícula de una esquina a otra haciendo sólo giros hacia arriba o hacia la derecha en $k-1$ filas y $n$ columnas es $$\binom{n+k-1}{k-1}$$

Answer 3

He aquí un método similar con funciones generadoras. El número de posibilidades es el coeficiente de $x^{70}$ en la serie formal $$ (1+x+x^2+x^3+\cdots)(1+x+x^2+x^3+\cdots)(1+x+x^2+x^3+\cdots)(1+x+x^2+x^3+\cdots) $$ ya que el coeficiente es la suma de todos los productos posibles de un término de cada serie cuyos exponentes suman $70$ . Pero lo anterior es $$ (1+x+x^2+x^3+\cdots)^4=\frac{1}{(1-x)^4}=\sum_{n\geq 0}\binom{n+3}{3}x^n $$ utilizando el hecho de que $\sum_{n\geq 0}\binom{n+k}{k}x^n=1/(1-x)^{k+1}$ para las funciones generadoras. Así, el coeficiente de $x^{70}$ es $\binom{73}{3}$ .