Combinatoria: El Uso De La Inclusión-Exclusión Principio

Question

No estoy seguro de cómo empezar esto. Me han dicho que el uso de la inclusión-exclusión, pero no sé qué propiedades para su uso.

Intuitivamente, quiero resolver el problema como este:

$E_1$ = 1 persona sale de la parada 1, 2 personas salir de la parada 1, 3 personas a salir de la parada 1,$\cdots$,5 personas salir de la parada 1 (debe tener al menos 5 a la izquierda para el resto de las paradas)

$$\binom {10} 1 + \binom {10} 2+ \cdots+ \binom {10} 5$$

$E_2$ = si 1 persona $E_1$, 1 persona sale de la parada 2, 2 personas salir de la parada 2,$\cdots$,4 personas salir de la parada 2

$$\binom 9 1 +\cdots + \binom 9 4$$

si 2 personas dejadas $E_2$, 1 persona sale de la parada 2, 2 personas salir de la parada 2,$\cdots$,3 personas a salir de la parada 2

$$\binom 8 1 + \binom 8 2 + \binom 8 3$$

...etc.

Pero no estoy seguro de cómo vincular cada uno de los eventos desde el último evento de manera que se cumplen las condiciones, lo que me lleva a pensar que estoy mal, muy mal.

Answer 1

Usted no puede agregar hasta las posibilidades de la primera parada, como hizo en el

$$\binom{10}1+\binom{10}2+\binom{10}3+\binom{10}4+\binom{10}5$$

debido a que cada una de estas posibilidades las hojas de un número diferente de posibilidades para el resto de las paradas.

Desde que le dijeron a la inclusión-exclusión, voy a asumir que los pasajeros son distinguibles, ya que de lo contrario sólo sería una de las estrellas y las barras de problema. Para el caso con distinguibles de los pasajeros mediante la inclusión-exclusión, se puede razonar de la siguiente manera: Hay $6^{10}$ formas de la $10$ a las personas a bajar en la $6$ se detiene. Sin embargo, eso también cuenta de los casos, con paradas donde nadie sale. Así que usted tiene que restar $6\cdot5^{10}$, donde el $6$ $6$ diferentes posibilidades para una parada donde nadie se baja y el $5^{10}$ es por la forma en que el $10$ de la gente puede bajarse en el resto de $5$ se detiene. Pero ahora te has restado de los casos con dos paradas, donde nadie sale dos veces, así que tienes que añadir a $\binom62\cdot4^{10}$, donde el $\binom62$ $\binom62$ diferentes posibilidades para los dos paradas, donde nadie se baja y el $4^{10}$ es por la forma en que el $10$ de la gente puede bajarse en el resto de $4$ se detiene. Continuar como esta, tienes

$$6^{10}-6\cdot5^{10}+\binom62\cdot4^{10}-\binom63\cdot3^{10}+\binom64\cdot2^{10}-\binom65\cdot1^{10}=16435440\;.$$

Answer 2

Sumando los coeficientes binomiales en que manera se ve raro de trabajo, dado que usted necesita para tener en cuenta el número de formas en que el acuerdo puede ser terminado (si usted pospone hasta más tarde, tendrá una contabilidad pesadilla).

Sugerencia: ¿Cuál es el número total de maneras en que los pasajeros pueden salir (ignorando la restricción en las paradas sin salir de pasajeros)? ¿Cómo puede ser modificado para dar cuenta de la restricción impuesta por la pregunta?

[En realidad, la respuesta a esta pregunta depende de lo que cuenta como una distinta configuración, que no está claro a partir de aquí la cuestión. E. g. son personas ilustres (si la persona existe en la parada 1, es lo mismo como si a la persona B existe en la parada 1?). Hacer que dejar el tren en algún orden? Voy a asumir que usted puede resolver esto.]

Answer 3

Alternativamente, usted puede utilizar los números de Stirling del segundo tipo.

Este problema puede ser modelado como dividiendo $n$ distintos objetos en $r$ grupos distintos (al menos uno en cada grupo) está dada por $$r! \times \left\{\begin{matrix} n \\ r \end{matrix}\right\}$$

Así, obtenemos $ 6! \times \left\{\begin{matrix} 10 \\ 6 \end{matrix}\right\} = 16435440$