Considere el siguiente problema:
En una ruta ferroviaria de 18 estaciones, ¿de cuántas formas puede parar un tren en 4 estaciones para que haya al menos 2 y como máximo 6 estaciones entre dos de ellas?
El anterior es el problema sobre el que tengo una pregunta. Mientras tanto, considere otro problema similar:
Una caja contiene 10 bolas rojas, 12 amarillas y 8 verdes. De cuántas maneras se pueden seleccionar 14 bolas si se debe seleccionar al menos una bola de cada color?
El anterior es un problema de palos y estrellas con un límite superior en el número de estrellas entre dos palos. Podemos reducir el problema anterior a permutar 2 palos (3 colores) y 11 estrellas (tomando 1 bola roja, 1 amarilla y 1 verde de las 14 necesarias). El número total de permutaciones es $13 \choose 2$ . De esto restamos los casos ilegales como el siguiente:
$$**********|*|$$
donde el espacio a la izquierda del primer palo representa las bolas rojas. Obsérvese que aquí hay 10 estrellas, pero es evidente que sólo tenemos 9 bolas rojas en nuestro presupuesto. Hay dos formas de que se produzca este caso ilegal en particular, y podemos encontrarlas permutando todo lo que hay a la derecha del primer palo (hay $2 \choose 1$ permutaciones). Otro caso ilegal:
$$***********\space |\space |$$
Número total de permutaciones de este caso ilegal = $1 \choose 1$
Podemos repetir el proceso anterior para las bolas verdes, de las que sólo podemos coger 7. (Todo lo que está a la izquierda del primer palo son ahora bolas verdes). El número total de permutaciones en las que hay más de 7 bolas verdes es ${4 \choose 1} + {3 \choose 1} + {2 \choose1} + {1\choose 1} $ .
Por último, restamos el número de permutaciones ilegales del número de permutaciones totales para obtener: $${13 \choose 2} - {2 \choose 1} - {1 \choose 1} - {4 \choose 1} - {3 \choose 1} - {2 \choose 1} - {1 \choose 1} = 65 \text{ legal cases}$$
Mi profesor utiliza la expansión binomial para resolver la mayoría de los problemas combinatorios, incluido éste (encuentra el coeficiente de una determinada potencia de $t$ en un $p(t)$ ). No me gusta su método porque no es nada intuitivo. Sin embargo, mi propio método funciona sólo porque el pedir de los palos no era importante (consideramos que todo lo que estaba a la izquierda del primer palo eran bolas rojas en el primer caso y bolas verdes en el otro). No funcionará cuando se cuenten las estaciones.
Para ilustrar lo que quiero decir, considere lo siguiente:
Quita 6 estaciones de 18, ya que debe haber al menos 2 estaciones entre cada una de las 4 estaciones seleccionadas. Ahora, nuestro problema se simplifica: dejemos que las cuatro estaciones estén representadas por palos y que las estaciones entre ellas sean estrellas; hallemos el número de permutaciones en las que hay entre cero y cuatro estrellas entre dos palos cualesquiera. Por ejemplo, se permiten éstas:
$$*|**|**|**|*$$ $$*****|*|**||$$
Pero esto no está permitido: $$|******|**||$$
¿Cómo puedo modificar mi método para resolver este problema? También se aprecian otros enfoques combinatorios.
