[Math] In how many ways can 5 boys and 3 girls be seated in a row such that no two girls are together

combinatoricspermutations

I've been trying to solve this permutation problem. I know that it's been posted on this site before, but my question is about the specific approach I take to solving it.

Here's what I thought I'd do : I could first figure out the total number of permutation where AT LEAST $2$ girls are together, and then subtract this from the total number of permutations.

Now, the total number of ways in which the students can be seated is obviously $^8\mathbf{P}_8$, or $8!$.

For the total number of permutations where at least $2$ girls are together, I first figured out that if I take $2$ girls as $1$ object, I can seat them in a total of $ 7 $ ways.

To this I multiplied the total number of way in which $2$ out of $3$ girls can be chosen. Thus I had $ 7 \times ^3\mathbf{P}_2 $, or $ 6 \times 7$

Finally, to this I multiplied the total number of permutations for the seating arrangement of the remaining students, to get $7 \times 6 \times ^6\mathbf{P}_6 $, or $ 6 \times 7!$.

Finally, I subtracted the number of permutation where AT LEAST 2 girls are seated together ($6 \times 7!$), from the total number of permutations of possible seating arrangements ($8!$).

Thus, I have $8! – 6 \times 7!$, or $7!(8-6) = 10080$.

BUT, the answer given in my book, and online, is 14400.

I want to know where my problem solving logic is wrong and if my calculation is wrong ?

Thanks.

Best Answer

You're overcounting the number of ways "at least two" girls can sit together, because for example

 Boy1 Boy2 Girl1 Girl2 Girl3 Boy3 Boy4 Boy5

is produced twice: Once considering Girl1 Girl2 as the unit, and once considering Girl2 Girl3 as the unit. This means that you're subtracting too large a number from $8!$, leading to a too small final result.

What you're doing is an inclusion-exclusion count, and for those you generally need to keep adding correction terms with alternating signs for ever more special cases.

An easier way to count is to start by finding all the allowed "gender sequences", without respect to which boys and girls are where. Afterwards you can multiply by $5!3!$ do distribute the actual children on the chairs.

To count the gender sequence, start by considering the three girl positions. The two first of them need to have at least one boy immediately to the right, so we have

  ... G B ... G B ... G ...

Now we have to distribute the three remaining B positions in among the four parts noted .... That's a stars-and-bars problem with $\binom{3+4-1}{3}$ possible outcomes.

So the total count you're looking for is $$ \binom{6}{3} \cdot 5!\cdot 3! $$

Related Question