Permutation and Combination

**jjc** · February 15th 2008, 10:02 PM

How many ways can you arrange 8 people in a row so that any two of the three people, A, B and C are together and all 3 of them cannot be together? The answer gives as (3C2 x 2! x 7!) - (3! x 6!) - (3C2 x 2! x 6C1 x 5!) = 21600

why?

**mr fantastic** · February 15th 2008, 11:41 PM

Originally Posted by jjc

How many ways can you arrange 8 people in a row so that any two of the three people, A, B and C are together and all 3 of them cannot be together? The answer gives as (3C2 x 2! x 7!) - (3! x 6!) - (3C2 x 2! x 6C1 x 5!) = 21600

why?

Well, my reasoning would be:

(a) Get how many arrangements have any two of A, B or C sitting together and don't worry about whether the third is with them or not.

(b) Get how many arrangements have all three of A, B and C sitting together.

Then subtract (b) from (a) ....

(a) = (number of ways of choosing a 'unit' of two from the three) times (number of ways of arranging within the 'unit') times (number of ways of arranging the 'unit' and the remaining six people) = ${3 \choose 2} \, 2! \, 7!$

(b) = (number of ways of arranging within a 'unit' of three) times (number of ways of arranging the 'unit' of three and the remaining five people) = $3! \, 6!$

So I get ${3 \choose 2} \, 2! \, 7! - 3! \, 6!$

At the moment I can't really see where the third term comes from .... someone better at arranging than I am might jump in and explain .....

**Soroban** · February 16th 2008, 03:27 AM

Hello, jjc!

I agree with Mr. F . . . I don't understand that third term.

How many ways can you arrange 8 people in a row
so that any two of the three people, A, B and C are together
and all 3 of them cannot be together?

The answer is: . $\left[{3\choose2}\cdot2!\cdot7!\right) - [3!\cdot 6!] - \underbrace{\left[{3\choose2}\cdot 2!\cdot {6\choose1} \cdot 5!\right]}_{{\color{red}???}} \;= \;21,600$

My reasoning is the same . . .

Select two of them to sit together.
There are: . ${\color{blue}{3\choose2}}$ ways . . . say, $A$ and $B,$
. . They can be ordered in ${\color{blue}2!} = 2$ ways: . $AB$ or $BA.$

Duct-tape the two together.
. . There are 7 "people" to arrange: . ${\color{blue}7!}$ ways.

Hence, there are: . ${\color{red}{3\choose2}(2!)(7!)}$ ways for some two to sit together.

But this includes the cases where all three sit together.
. . We must deduct these cases.

Duct-tape the three together.
. . The three can be ordered in ${\color{blue}3!}$ ways.
There are 6 "people" to arrange: ${\color{blue}6!}$ ways.

Hence, there are: . ${\color{red}(3!)(6!)}$ ways for all three to sit together.

Therefore, there are: . ${3\choose2}(2!)(7!) - (3!)(6!) \;=\;\boxed{{\bf{\color{blue}25,920}} \text{ ways}}$

**Plato** · February 16th 2008, 04:56 AM

I agree with the other two about the third term. But I disagree about the answers they came up with.
The given answer, 21600, is correct.

There are 6 ways, (AB, AC, BA, BC, CA, CB), for two of the three to sit together.
Now we have in the pattern _D_E_F_G_H_ six places to put one of those pairs and the five places to put the remaining third-person out so that the three are not seated together.
That gives $(6)(6)(5)(5!)=21600$ .

So I think the given answer is correct, but I cannot understand the why of makeup of those three terms.

Post Script
There are ${6 \choose 3}(5!)(3!)$ ways to separate A, B, & C.
There are $(8!)-{6 \choose 3}(5!)(3!)$ ways that at least two of those are together. But this number also includes cases in which all three are together.
So There are $(8!)-{6 \choose 3}(5!)(3!)-(3!)(6!)=21600$ .

**mr fantastic** · February 16th 2008, 12:39 PM

Originally Posted by Plato

I agree with the other two about the third term. But I disagree about the answers they came up with.
The given answer, 21600, is correct.

There are 6 ways, (AB, AC, BA, BC, CA, CB), for two of the three to sit together.
Now we have in the pattern _D_E_F_G_H_ six places to put one of those pairs and the five places to put the remaining third-person out so that the three are not seated together.
That gives $(6)(6)(5)(5!)=21600$ .

So I think the given answer is correct, but I cannot understand the why of makeup of those three terms.

Post Script
There are ${6 \choose 3}(5!)(3!)$ ways to separate A, B, & C.
There are $(8!)-{6 \choose 3}(5!)(3!)$ ways that at least two of those are together. But this number also includes cases in which all three are together.
So There are $(8!)-{6 \choose 3}(5!)(3!)-(3!)(6!)=21600$ .

Arrangements under restriction always cause trouble - to me, anyway.

I'm sorry Plato - I don't follow your reasoning here. Or rather, I don't see why your reasoning (which I don't follow) is correct whereas the reasoning of Soroban and myself is wrong ..... I guess I've got a problem with the Minority Report

(Mind you, I've only just woken up and am eating breakfast ....)

**Plato** · February 16th 2008, 01:17 PM

Originally Posted by mr fantastic

I don't see why your reasoning (which I don't follow) is correct whereas the reasoning of Soroban and myself is wrong ..... I guess I've got a problem with the Minority Report

Well my answer does agree with the answer given by the text. I got the same by two different ways.
It took me a moment to realize the mistake in yours and Soroban’s reasoning.
Here it is.
The difference in the two solutions is $25920 - 21600 = 4320$ .
That happens to be the same numbers as $6(6!)$ .
That means that you both have counted the three sitting together twice.
Here is how that was done. Think of counting the strings that begin “ABC…”
That string is counted once when counting strings containing the pair AB: $\boxed{AB}C \cdots$ .
The same string is counted again when you both counted stings using the pair BC: $A\boxed{BC} \cdots$ .
Thus in counting the pair strings ${3 \choose 2}(6!)(2)$ you have counted the strings containing the three together twice each.
Now ${3 \choose 2}(6!)(2) - (2)(6)(6!)=21600$ .

Thread: Permutation and Combination

LinkBack

Thread Tools

Display