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.
Best Answer
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\;.$$