2
$\begingroup$

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?

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

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.

$\endgroup$
2
  • $\begingroup$ but the question says ...75 people enter the train from London with 75 different tickets..., is this, not a contradiction according to your last paragraph? They say all boarding is from London. $\endgroup$
    – mnulb
    Aug 25 '18 at 6:01
  • $\begingroup$ What the question says is that the passengers board a train that is traveling from London to Cambridge with twelve intermediate stops. It does not say that they all board in London. $\endgroup$ Aug 25 '18 at 7:34

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.