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.

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?

Every person can pick a seat. So there is 20! seat arrangements. Something is wrong with this reasoning, what is it about five cars which makes me miscount the number of ways the ride can begin?

If, instead of a roller coaster there was a ferris wheel one wouldn't be able to apply the "pick a seat" logic because it's the wheel that is round, not the seats(not $19!$) and a natural choice would be to put people in groups of 4 and then permute the groups on the wheel $5!/5$ and then permute the people in the cars, ${4!}^{5}$.

Which finally gives us $20!4!$ ways the ride can begin.

Now, I'm wondering, if the same approach was taken(split into groups) for the roller coaster there would be $20!5!$ ways to start a ride.

Equivalent problem would be -> There's a giant concert hall with 100 seats. There are 50 blue and 50 white seats. In how many ways can the concert begin if 100 people want to listen to it?

I would say 100! but since colors can be interpreted like cars this would mean that splitting people in 2 groups of 50, picking a car of colored seats would take 2! the final solution with the ferris wheel approach would give me $100!2!$.

I have no idea which of the 100! ways I lost in the first solution.

What I'm asking is what and where is the flaw and then what is the generalized solution?

share|improve this question
    
Do you know for a fact that your 20-factorial answer to the original question is wrong? Do you know what the "right" answer is supposed to be? –  Gerry Myerson Dec 30 '12 at 2:46
    
I wasn't sure which approach was right... –  Looft Dec 30 '12 at 11:28
add comment

3 Answers

up vote 2 down vote accepted

The mistake that you made with the Ferris wheel is as follows:

You started off picking the groups of 4 people as ${ 20 \choose 4} \times { 16 \choose 4} \times { 12 \choose 4} \times {8 \choose 4} \times { 4 \choose 4}$. However, choosing ABCD first and then EFGH, is the same as choosing EFGH first and then ABCD. As such, you over counted $5!$ times, and hence need to account for that. This is where the 'extra' 5! comes from in your 'equivalent roller coaster'.

The simple way to see why this is wrong, is to think of how many ways there are to choose 5 groups of 1 people from a group of 5. Clearly, there is only 1 way to do so. However, if we were to use your explanation, there are 5 ways to pick the first person, 4 ways to pick the second, 3 to pick the third, 2 to pick the fourth, 1 to pick the fifth. What you are doing, is permuting the 5 groups, as opposing to choosing the 5 groups.


This should be enough information for you to fix your 'concert hall' issue. Being confused between permuting and choosing of groups is an extremely common situation. It occurs because you do not consciously realize that you're actually introducing order into that groups.

share|improve this answer
    
Yep, this clears things up. My first solution to the problem was 20! and then 20! - 5*4*3 for the condition. For the ferris wheel I just divided things by 5. I found a solution to the ferris wheel problem on a ksu page and thought because the solutions were official that they were correct. But I then tried seeing what was wrong with their approach and what was wrong with mine and couldn't see the mistake in my approach but at the same time couldn't see it in theirs. What your answer said is that the picking of groups is already permutation so there is no need to permute again. –  Looft Dec 30 '12 at 11:38
add comment

In the spirit of Gerry Myerson's comment, you need to define what makes one configuration different from another. If the two people in the front seats of a car switch places, is that different? Are the cars numbered so if everybody moves one car aft you can tell the difference? If the answer to both of these is yes, then $20!$ is correct. If not, you need to divide by the number of times that each configuration is counted. So if you don't care if a rider is on the left or right in a car, there are $10$ pairs that can switch so you divide by $2^{10}$. If the cars are interchangeable, you can rotate $5$ ways, so you divide by $5$. Without a clear question, there is no clear answer.

share|improve this answer
    
The cars of the ferris wheel are interchangable, so there's definitely division by 5. People can switch places and that counts. This problem was taken from the Introductory Combinatorics (Brualdi). That is the original wording and yep, I do agree that it might not be clear enough. –  Looft Dec 30 '12 at 11:22
add comment

Ok, This is how I would fill the ferris wheel. Pick the first four people. you can pick 20 in the first seat. 19 in the second,18 in the third and 17 in the fourth. Then turn the Ferris wheel to put the fifth person inside (16 options). Therefore there are still 20! ways for the ferris wheel to start.

share|improve this answer
1  
You would have to divide by 5, because he doesn't care about the rotational order of the cars (while yours does with the idea of 'for the ferris wheel to start'). It's similar to the question of sitting friends around the table, where rotations don't count. Also, you're not explaining the flaw of his argument. –  Calvin Lin Dec 30 '12 at 2:52
add comment

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.