# Permutations Problem

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.

-
how many way could Micah and Loretta sit together? –  Mark May 3 '11 at 0:38

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

-
I do believe my LaTeX skills kind of fell off on that last equation... Help? O_o –  Nicolas Villanueva May 3 '11 at 0:52
Use this instead: 2 \cdot {3!}^2 \cdot \left[ 3 \cdot {2 \choose 1} + 1 \cdot {3 \choose 1} \right]. The choose notation needs to be encased in brackets. –  mixedmath May 3 '11 at 0:58
@mixedmath Well played... –  Nicolas Villanueva May 3 '11 at 1:00
I'm not sure i understand the structure of {2 \choose 1} type of numbering, can you elaborate? However I did post this on yahoo answers as well and got a fairly complete answer, still a bit sketchy though as permutations aren't my strong suit. –  mHo2 May 3 '11 at 1:12

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.

-
Oh sorry I do not know the number of cases when they are sitting together, sorry for the mixup! –  mHo2 May 3 '11 at 1:13

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.

-

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

-

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

-
I just realized this is a month old question. Should see the date on front page questions as well. –  kuch nahi Jun 16 '11 at 22:51
the problem was that Matt answered the question (fairly new here), which "bumped it" to the front page of "active" questions, ... you weren't the only one who answered it since...no harm done (by your answering it!). –  amWhy Jun 17 '11 at 19:09