Permutations Problem

Question

I'm having a bit of an issue with solving a permutations problem

Find the number of ways in which $4$ boys and $4$ girls can be seated in a row of $8$ seats if they sit alternately. Okay, well.. Simple enough, after solving the permutations of both cases I get $1152$ permutations

There is a boy named Micah and a girl named Loretta in problem number $4$, and they cannot be seated next to each other or else they will fight. How many permutations are there now?

I'm completely stuck on this one, without any idea on how to start except for getting the number of permutations where they are sitting together.

Any help would be appreciated (not just an answer please!)

Answer 1

Notice that if we have boys occupying every other seat, there are 2 total arrangements for boys and girls. If I take the arrangement where the first spot is a boy, we will have the following: $${\_\_}_B \cdot {\_\_}_G \cdot {\_\_}_B \cdot {\_\_}_G \cdot {\_\_}_B \cdot {\_\_}_G \cdot {\_\_}_B \cdot {\_\_}_G$$ From here we can break down the problem into 2 cases. Case 1: Micah sits at the end of the table $$M \cdot {\_\_}_G \cdot {\_\_}_B \cdot {\_\_}_G \cdot {\_\_}_B \cdot {\_\_}_G \cdot {\_\_}_B \cdot {\_\_}_G$$ For which there are $3\choose{1}$ ways of choosing a seat for Loretta. Case 2: Micah doesn't sit at the end of the table, for example $${\_\_}_B \cdot {\_\_}_G \cdot M \cdot {\_\_}_G \cdot {\_\_}_B \cdot {\_\_}_G \cdot {\_\_}_B \cdot {\_\_}_G$$ For which there are $2\choose{1}$ ways of choosing a seat for Loretta. Since all that's left is to permute the 3 remaining boys and girls we have the final solution to be $$ 2 \cdot {3!}^2 \cdot \left[ 3 \cdot {2 \choose 1} + 1 \cdot {3 \choose 1} \right] $$

Answer 2

Hint: If you know the number of permutations possible when the 8 boys and girls sit alternately, and you know the number of cases possible when they are sitting next to each other (which you indicated you knew) - then you already know how many cases there are when they are not sitting next to each other!

Note that (# cases where Micah sits next to Loretta) + (# cases where Micah does not sit next to Loretta) = total number of cases.

Answer 3

An easy solution to this problem would be:

take the number of permutations were boys & girls sit alternatively (Z)

minus

the number of configurations were the two people sit next to each other (Y = 2(8-1))

times

the answer to problem 4, if you instead had 3 boys, 3 girls, and 6 seats (X).

Z - (Y(X))

Of course, this is all assumuning you know how to solve problem 4.

Answer 4

Here is a probabilistic argument: The probability that Micah sits at the end of the row is ${1\over 4}$, and in this case the probability that Loretta sits next to him is ${1\over4}$ also. In the remaining ${3\over 4}$ of the cases the probability of Loretta sitting next to Micah is ${1\over 2}$. It follows that the fraction of "bad cases" is ${1\over4}\cdot{1\over4}+{3\over4}\cdot{1\over2}={7\over 16}$, therefore the number of allowed seatings is ${9\over 16}\cdot 1152=648$.

Answer 5

Number of ways Micah and Loretta can sit together: $7\times 2!$

$$ML------$$ $$-ML-----$$ $$--ML----$$ $$---ML---$$ $$----ML--$$ $$-----ML-$$ $$------ML$$ $$------LM$$ $$-----LM-$$ $$----LM--$$ $$---LM---$$ $$--LM----$$ $$-LM-----$$ $$LM------$$

In the dashes, 3 boys and 3 girls can be seated in $3!\times 3!$ ways, so by the product rule, the total number of ways that Micah and Loretta can be sitting together is $7\times 2!\times 3! \times 3!$

Next you need to realize that the the number of seating where ML are together and the number of seatings that ML are seperate are mutually exclusive and their sum is the total number of ways (i.e the first part). So you should get:

$$4!\times 4!\times 2 -7\times 2!\times 3! \times 3! =648$$