Trip from London to Cambridge.

I attempted to solve a combinatorical question (here):

A train going from London to Cambridge stops at 12 intermediate stops. 75 people enter the train from London with 75 different tickets of the same class. No. of different sets of tickets they may be holding is:___

Please point out why my solution is incorrect.

Let number of persons for $i^{th}$ stations be $x_i\implies 0\leq x_i\leq 75$ where $i\epsilon[1,12]$.

So the number of non-negative integral solutions of $$x_1+x_2+\cdots x_{12}=75$$

is coefficient of $x^{75}$ in $$(x^0+x^1+x^2+\cdots x^{75})^{12}$$

$$= (1-x^{76})^{12}\cdot(1-x)^{-12}$$

which is equal to ${75+12-1\choose{12-1}}={86\choose{11}}$.

This doesn't match the answer given which was ${91\choose{75}}$. Can someone please explain why?

What did my solution count? And what does the question want me to count?

• To begin with, "12 intermediate stops" so you are missing one (the final) station. Dec 22 '17 at 6:09
• Then, you are looking at the compositions of people, not No. of different sets of tickets Dec 22 '17 at 6:13

Since there are $12$ intermediate stops, there are a total of $14$ stations on the route, including London and Cambridge. A ticket is determined by choosing the two stations where the trip begins and ends. Hence, there are $$\binom{14}{2} = 91$$ possible tickets. Since the passengers hold $75$ of these, the number of different sets of tickets they could be holding is $$\binom{91}{75}$$
The equation $$x_1 + x_2 + x_3 + \ldots + x_{12} = 75$$ counts the number of ways $75$ identical objects can be placed in $12$ distinct bins. While you could use this equation to determine how many ways there are for $75$ people who board the train in London to exit the train at the $12$ intermediate stops, that is not what the question is asking.