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.

This is question from my aptitude test booklet and would appreciate assistance in clarifying my doubt.

In how many ways can five boys and six girls be seated in a row such that John, one of the boys, is seated at one of the extreme ends and no two boys are adjacent to each other?

The way I approached it is like this.

I make the boys sit in a row with John at one corner J B2 B3 B4 B5

This can be done in 2 x 4! ways, john being at either extremes.

Next to make sure no two boys sit together, I select 4 of the 6 girls and make them occupy the seats in between the boys.

J G1 B2 G2 B3 G3 B4 G4 B5

This can be done in 6C4 x 4! ways.

Finally, the two girls I am left with can occupy one of the 9 and 10 remaining spots in between respectively.

That gives me 2 x 4! x 6C4 x 4! x 9 x 10 = Terribly wrong answer

Please explain on where I went wrong. Thanks!

share|improve this question

4 Answers 4

up vote 2 down vote accepted

Let $\times$ represents a girl and $o$ represents a boy.

Then, first place the girls as $ .\times . \times.\times.\times.\times.\times.$ where $.$ represents $o$ or no one. Now , Since John is at extreme, he has two choices while other $4$ boys have $6$ choices giving total of ${2\choose 1}{6\choose 4}$. Now permute all the boys independently(except John) and girls independently giving total of ${2\choose 1}{6\choose 4}4!6!$ sitting arragements.

share|improve this answer
    
+1, I think that this is the right answer. –  Quixotic Sep 12 '12 at 15:04
    
Thanks for the answer. The answer booklet also said the same thing about starting with arranging the girls first. I see it is definitely easier to solve that way. –  user40143 Sep 17 '12 at 11:43

You over counted some possibilities when you chose $4$ of the $6$ girls and then placed the remaining girls arbitrarily. For example, you can choose Alice and Jane to occupy the first two spots and then place Sandy behind Alice, but this is the same as choosing Sandy and Jane to occupy the first two spots and placing Alice in front of Sandy.

You need to take care that there are no repetitions and redundancies between the various steps of your counting. Perhaps as a hint, for this problem in particular it would probably be easier to permute the girls and then place the boys in between.

share|improve this answer
    
I will more careful from now on. Thanks :) –  user40143 Sep 17 '12 at 11:58

Another way to think about it is to first place John at the left end (we will double for the right end later). Every other boy needs a girl to his left, so pair them up. This can be done in $6 \cdot 5 \cdot 4 \cdot 3=\frac {6!}2$ ways. Now you have six people to put in order (four of whom are pairs), which can be done in $6!$ ways. Overall, $\frac {6!}26!\cdot 2=518400$

share|improve this answer
    
I like your approach too. Thanks a ton. Very helpful. –  user40143 Sep 17 '12 at 11:48

The last two girls should be restricted in where you seat them. If you place G5 between G1 and B2, you could as well have placed G5 between J and B2 and then G1 between J and G5. Therefore place G5 at any of the $9-4$ positions not to the left of a boy, then G6 at any of the $10-4$ positions not ot the left of a boy. I hope the resulting $2\cdot 4!\cdot {6\choose 4}\cdot 4!\cdot 5\cdot 6$ is the answer that was expected.

Alternatively: Seat the boys with $2\cdot 4!$ possibilities. Add four empty chairs to separate them. Of the 5 positions to the right of boys select either two different ($5\choose 2$ possibilities) and add a chair, or select one (5 possibilities) and add two chairs. Then place the 6 girls on the empty chairs ($6!$). In total: $2\cdot 4!\cdot({5\choose 2}+5)\cdot 6!$

share|improve this answer
    
Thanks for pointing out where I went wrong. Helps :) –  user40143 Sep 17 '12 at 11:57

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.