A railway carriage will accommodate 5 passengers on each side

  • Thread starter Thread starter RChristenk
  • Start date Start date
  • Tags Tags
    Combinatorics
AI Thread Summary
The discussion revolves around calculating the seating arrangements for passengers in a railway carriage with specific restrictions. The initial calculation yielded 504,000 arrangements, while a second approach focused on unrestricted passengers resulted in an incorrect figure of 352,800 due to misinterpretation of dependencies among passengers. The correct method involves selecting backward-facing seats and accounting for the permutations of both restricted and unrestricted passengers. Ultimately, the accurate calculation was confirmed to be 3,024,000 after correcting a miscalculation in the combination of unrestricted passengers. The thread emphasizes the importance of understanding dependencies in combinatorial problems.
RChristenk
Messages
73
Reaction score
9
Homework Statement
A railway carriage will accommodate 5 passengers on each side (one side faces the engine, and one side faces backwards). In how many ways can 10 persons take their seats when two of them decline to face the engine, and a third cannot travel backwards?
Relevant Equations
Elementary combinatorics
The straightforward way to solve this question:

1. Two passengers decline to face the engine: ##^5C_2 \cdot 2! = 20##
2. One passenger cannot travel backwards: ##^5C_1 \cdot 1! =5##
3. The remaining seven passengers can sit in any order in the remaining seven seats: ## 7! ##

Multiply 1,2,3 together and get the correct answer 504000.

My question is what if I focused on the seven passengers that don't have any restrictions?
1. For the five seats facing backwards, from seven non-restricted passengers three can be chosen: ##^7C_3 \cdot 3! = 210##
2. For the five seats facing the engine, from seven non-restricted passengers four can be chosen: ##^7C_4 \cdot 4! = 840##
3. The two passengers that must face the back: ##2!##

Multiply 1,2,3 together and I get 352,800 which is wrong. Where did I make the mistake? Thanks.
 
Physics news on Phys.org
The three passengers facing backwards are not independent of the four passengers facing forwards: no passenger can do both! Also, a backwards facing seat could be occupied by one of those three undecided passengers, but also by one of the two who must face backwards. Thus, once the three undecided passengers who will face backwards are chosen, there are five people who can occupy any particular backward-facing seat. Your method fixes in advance which of the backward facing seats the three passengers (in some order) will sit in, with the other two taken (in some order) by the passengers who insist on facing backwards.

So: There are {}^5C_3 ways to select the backward-facing seats which the three chosen passengers will sit in. There are {}^7P_3 = 7!/4! = {}^7C_3 \cdot 3! ways in which three of the seven flexible passengers can occupy those seats. The other four passengers must face forwards; there are {}^5C_4 ways to choose the seats they sit in, and 4! ways for them to occupy the seats. Of the remaining passengers, the two who must face backwards can occupy the two remaining seats in 2! ways, and the one passenger who must face forwards takes the only remaining seat.

The number of permutations is then <br /> {}^5C_3 \cdot {}^7P_3 \cdot 2! \cdot {}^5C_4 \cdot 4! = \frac{5!}{3! \cdot 2!} \cdot \frac{7!}{4!} \cdot 2! \cdot \frac{5!}{4! \cdot 1!} \cdot 4! = 7! \cdot \frac{5!}{3!} \cdot \frac{5!}{4!} = 7! \cdot {}^5P_2 \cdot {}^5P_1.

It is easier to observe that choosing 4 of the 7 flexible passengers determines which way they all face, and then there are 5! ways for each group to order themselves, making {}^7C_4 \cdot (5!)^2 permutations,
 
Last edited:
What you said in the end makes intuitive sense, but I calculated ##^7C_4 \cdot (5!)^2=3024000##, so why is the numerical answer wrong here?
 
RChristenk said:
What you said in the end makes intuitive sense, but I calculated ##^7C_4 \cdot (5!)^2=3024000##, so why is the numerical answer wrong here?
Check your calculation!
 
Ah it is correct indeed. I miscalculated ##^7C_4##.
 
Back
Top