Combinatorics: Using Inclusion-Exclusion Principle

Question

I'm not sure how to start this. I've been told to use inclusion-exclusion, but I don't know which properties to use.

Intuitively, I want to solve the problem like this:

$E_1$ = 1 person leaves stop 1, 2 people leave stop 1, 3 people leave stop 1,$\cdots$,5 people leave stop 1 (need to have at least 5 left for the rest of the stops)

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

$E_2$ = if 1 person left $E_1$, then 1 person leaves stop 2, 2 people leave stop 2,$\cdots$,4 people leave stop 2

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

if 2 people left $E_2$, then 1 person leaves stop 2, 2 people leave stop 2,$\cdots$,3 people leave stop 2

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

...etc.

But I'm not sure how to link up each event from the last event so that the conditions are satisfied, which leads me to think that I am terribly wrong.

Answer 1

You can't add up the possibilities for the first stop as you did in

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

because each of these possibilities leaves a different number of possibilities for the remaining stops.

Since you were told to use inclusion-exclusion, I'll assume that the passengers are distinguishable, since otherwise this would just be a stars and bars problem. To do the case with distinguishable passengers using inclusion-exclusion, you can reason as follows: There are $6^{10}$ ways for the $10$ people to get off at the $6$ stops. However, that also counts cases with stops where no-one gets off. So you have to subtract $6\cdot5^{10}$, where the $6$ is for $6$ different possibilities for a stop where no-one gets off and the $5^{10}$ is for the ways in which the $10$ people can get off at the remaining $5$ stops. But now you've subtracted cases with two stops where no-one gets off twice, so you have to add $\binom62\cdot4^{10}$, where the $\binom62$ is for $\binom62$ different possibilities for two stops where no-one gets off and the $4^{10}$ is for the ways in which the $10$ people can get off at the remaining $4$ stops. Continuing like this, you get

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

Answer 2

Summing binomial coefficients in that way looks unlikely to work, since you need to account for the number of ways the arrangement can be completed (if you postpone it until later, you'll have a bookkeeping nightmare).

Hint: What is the total number of ways the passengers may exit (ignoring the restriction on stops without exiting passengers)? How can it be modified to account for the restriction imposed by the question?

[Actually, the answer to this question depends on what counts as a distinct configuration, which is not clear from the question here. E.g. are people distinguished (if person A exists at stop 1, is this the same as if person B exists at stop 1?). Do they leave the train in some order? I'll assume you can sort this out.]

Answer 3

Alternatively you could use Stirling numbers of the second kind.

This problem could be modeled as dividing $n$ distinct objects into $r$ distinct groups (at least one in each group) is given by $$r! \times \left\{\begin{matrix} n \\ r \end{matrix}\right\}$$

So we get $ 6! \times \left\{\begin{matrix} 10 \\ 6 \end{matrix}\right\} = 16435440$