1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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! $$

$\endgroup$
0
$\begingroup$

Neglect for the moment the personality and just watch the gender.

First arrange girls in line so that there is an empty place between them. Then we put 2 boys between 1. and 2. and between 2. and 3. girl. To every ''good'' arrangement of gender we assign 6-couple so that between two girls we ''delete'' one boy, for example: $$ \circ \bullet \circ \bullet \circ \circ \circ \; \bullet \;\; \longmapsto \;\;\circ \bullet \bullet \circ \circ \;\bullet $$ This map is bijective, so we have totally ${6\choose 3}$ assigments. If we on black points arrange girls and on white boys we get all possibility: $${6\choose 3} \cdot 3!\cdot 5! = 120^2$$

$\endgroup$
0
$\begingroup$

The reason your answer is wrong is that your count of how many arrangements have at least two girls in consecutive seats is incorrect. When you subtracted those arrangements in which a pair of girls in consecutive seats, you subtracted those arrangements in which all the girls sit in consecutive seats twice, once when you designated the leftmost two girls as the pair and once when you designated the rightmost two girls as the pair.

One way to fix this is to subtract those arrangements in which exactly two girls sit in consecutive seats and then subtract those arrangements in which three girls sit in consecutive seats, as I did in this problem. However, a more straightforward fix is to use the Inclusion-Exclusion Principle.

There are $8!$ ways to arrange the eight children in a row. From these, we must exclude those seating arrangements in which at least two girls sit in adjacent seats.

A pair of girls sit in adjacent seats: There are $\binom{3}{2}$ ways to choose which girls will sit in a block of adjacent seats. We have seven objects to arrange, the block of two girls and the other six children, which we can do in $7!$ ways. The two selected girls can be arranged within the block in $2!$ ways. Hence, there are $$\binom{3}{2}7!2!$$ such seating arrangements.

However, as explained above, we have subtracted those seating arrangements in which all three girls sit in consecutive seats twice. We only wish to subtract them once, so we must add those arrangements back.

Two pairs of girls sit in adjacent seats: Since there are only three girls, this can only occur if the three girls sit in consecutive seats. We have six objects to arrange, the block of three girls and the five boys. The objects can be arranged in $6!$ ways. The girls can be arranged within their block in $3!$ ways. Hence, there are $6!3!$ seating arrangements in which all three girls are consecutive.

By the Inclusion-Exclusion Principle, the number of permissible seating arrangements is $$8! - \binom{3}{2}7!2! + 6!3! = 14400$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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