3
$\begingroup$

How to find the number of combinatorial arrangements with two conditions, if one of the conditions is itself dependent on the second? The question below will make it clearer.

The problem statement goes as follows:

A train going from station A to station B stops at nine intermediate stations. Six persons enter the train during the journey with six different tickets of the same class. Find the number of different sets of tickets they may have had.

The answer is $\displaystyle \binom{45}{6}.$

The main problem is that the passengers are allowed to board the train at the same station but they aren't allowed to leave at the same station. This makes the problem unsymmetric, so we cannot simply select six pairs of stations, or select the boarding stations for the six persons, and then select the stations where they get off. For example, if the person $1$ boards at station $3$, then he can depart at $6$ possible stations. But person $2$ if boards at the same station, has now only $5$ possibilities, and this would be even more complicated if he boarded the train at, say, station $4$ or $5$.

How do i accomodate the second condition also along with the first condition? Also, is there a simple way that justifies the question having such a simple answer format?

Thank you.

$\endgroup$
  • $\begingroup$ Is the ticket defined as i-j where i<j? $\endgroup$ – Alex Jun 28 '16 at 18:19
6
$\begingroup$

My view is that there are ${2+9 \choose 2}=55$ possible tickets since each ticket goes between two of the $2+9=11$ stations

The passengers have six of these so the answer should be ${55 \choose 6}=28989675$, but this is not the given answer

To get the given answer, you could interpret "enter the train during the journey" as meaning they do not get on at station A but might get off at station B, so there are ${1+9 \choose 2}=45$ possible tickets and so ${45 \choose 6}=8145060$ possibilities for choosing six of these

$\endgroup$
  • $\begingroup$ Thank you for your answer! $\endgroup$ – FreezingFire Jun 29 '16 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.