Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

An exercise from Introductory Combinatorics by Richard A.Brualdi:

A roller coaster has five cars, each containing four seats, two in front and two in back. There are 20 people ready for a ride. In how many ways can the ride begin? What if a certain two people want to sit in different cars?

Since we can assume the $5$ cars to be distinguishable,the number of ways to place people inside cars is simply $\dfrac{20!}{(4!)^5}$. But for each of these combinations,we need to choose who takes the front seats and who takes the back seats.The number of ways to do that is simply $\dbinom{4}{2}$.Also,we need to find the number of permutations of the people in each car(after choosing who will sit in the front),which is $2!2!$.Therefore the number of ways to begin the ride is just $$\dfrac{20!}{(4!)^5}\dbinom{4}{2}2!2!$$ I am not worried about the second part of the question because we can possibly use complementary counting for that.But is the answer to the first question right?I ask because it all seems very confusing whether I should multiply by $\dbinom{4}{2}$ or $\dbinom{4}{2}^5$ by considering each of the cases.Also,are there less confusing ways of approaching this problem?Any suggestion or hint will be greatly appreciated.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Your introduction of the factor ${4\choose2}2!2!$ specifies who sits where in only one car. You need to raise that factor to the fifth power, to account for all five cars.

Note, though, that ${4\choose2}2!2!={4!\over2!2!}2!2!=4!$, so the fifth power will entirely cancel the $(4!)^5$ in the $20!\over(4!)^5$, leaving just $20!$. This makes sense: If it matter exactly where people sit in the cars, then the number of arrangements amounts to assigning a different seat to each of the $20$ people, which is just $20!$.

Added in response to OP's comment: As to the second part, one way, as you note, is to count the number of ways to have the two people sit in the case car, which is $20\cdot3\cdot18!$, and subtract from $20!$. But another way is to have those two people -- let's call them Bob and Ted -- be the first two to take seats. If we seat Bob first, he has $20$ choices, but then Ted has just $16$. After that, it's $18\cdot17\cdots2\cdot1=18!$ ways to seat everyone else, for a total of $20\cdot16\cdot18!$ different seatings with Bob and Ted in different cars.

Note, this generalizes easily to more people who don't want to sit in the same car, say Bob and Carol and Ted and Alice: $20\cdot16\cdot12\cdot8\cdot16!$, whereas the subtraction approach gets messy.

Added yet later: There's one more approach that's worth mentioning. Have Ted be the very last person to sit. It's easy to see that Bob and the others have $20\cdot19\cdots3\cdot2=20!$ ways of sitting. No matter where Bob sits, the proability that the empty seat is in another car is $16\over19$, so the number of ways to keep Bob and Ted apart is

$${16\over19}\cdot20!=16\cdot20\cdot18!$$

share|improve this answer
    
Ah,of course,the last sentence was rather illuminating(and made me feel stupid for not seeing it). Thanks for the clear reply.However,the second question cannot be reformulated as follows:Find the number of ways to permute 20 distinguishable objects such that A and B do not come after one another.There seems to be more work to be done.We can first think about the cases where A and B do seat beside each other and then subtract it from the total cases.Is there a neater way? –  rah4927 Apr 9 at 12:04
    
Thank you for the addendum.I find the last method more elegant than the others in resolving the second problem. –  rah4927 Apr 9 at 14:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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