# problem with Combination and Permutation

Four married couples have bought 8 seats in a row for a concert. In how many ways can they be seated:

a)if each couple is to sit together?

(8)(1)(6)(1)(4)(1)(2)(1)

b)if all men sit together?

n-k+1=8-4+1=5

so, (5)(4! 4!)=5! 4!

c)If no man sits next to his wife ?(This is a non-trivial questions)

8*6*6*4*4*2*2*1=18432 ways

could you please check it for me ?

• a) and b) are correct. For c), I suggest using Inclusion/Exclusion. – André Nicolas May 24 '16 at 2:59
• Subtract $a$ from $8!$. – A---B May 24 '16 at 3:56
• @FaraadArmwood In the first question, there are $4!$ ways of arranging the couple and $2!$ ways of arranging each couple internally, so there are $4!2^4$ arrangements in which each couple sits together. The OP opted to choose a person to sit in the leftmost seat, sit that person's partner in the next seat, sit one of the remaining people in the leftmost open seat, sit that person's partner in the next seat, and so forth. For the second question, the block of five men can be treated as one object. Place the block among the four women, then arrange the men and arrange the women. – N. F. Taussig May 24 '16 at 9:36

a) and b) are correct.

For c), we will use Inclusion/Exclusion. There are $8!$ arrangements without restriction. From this we need to subtract the number of bad arrangements, where at least one couple are next to each other.

First we count the number of arrangements where Couple A are together. Tie them together with rope. There are then $7$ objects to be arranged. This can be done in $7!$ ways. Now untie Couple A. They can occupy $2$ different positions, for a total of $2\cdot 7!$. Multiply by $\binom{4}{1}$ for the number of ways to choose a couple. Our first estimate of the number of bad arrangements is $\binom{4}{1}\cdot 2\cdot 7!$.

However, this grossly overcounts the number of bad arrangements, for it double-counts, among others, the arrangements where Couple A and B are both next to each other. An analysis similar to the previous one shows that there are $2^2\cdot 6!$ arrangements in which Couple A and B are together. Thus our adjusted count for the number of bad arrangements is $\binom{4}{1}\cdot 2\cdot 7!-\binom{4}{2}\cdot 2^2\cdot 6!$.

However, we have subtracted too much, for we have subtracted one too many times, for example, the arrangements where couples A, B, C are together. Adjusting for this gives the adjusted count $\binom{4}{1}\cdot 2\cdot 7!-\binom{4}{2}\cdot 2^2\cdot 6!+\binom{4}{3}\cdot 2^3\cdot 5!$.

A final adjustment needs to be made, we must subtract the $\binom{4}{4}\cdot 2^4\cdot 4!$ arrangements in which all couples are together. This will give us the total number of bad arrangements, and now we are nearly finished.

a)if each couple is to sit together?

$$4!~2!^4 = 8\cdot 6\cdot 4\cdot 2$$ $\checkmark$ LHS counts ways to arrange 4 couples, then ways to arrange partners in each couple.   RHS counts ways to select a person, their partner, another person, their partner, and so on.   Either way is okay (but see part c).

b)if all men sit together?

$$5!~4!$$

$\checkmark$ Count ways to arrange the women and a unit, and men within the unit.

c)If no man sits next to his wife ?(This is a non-trivial questions)

It is as easy as PIE.   Use the principle of inclusion and exclusion.   Count all the ways to arrange everybody, exclude ... , include ..., exclude ... , and finally include ways to select all four couples and arrange such that they each sit together.

$$8! - \underline\qquad+\underline\qquad-\underline\qquad+\binom{4}{4}4!~2!^4$$

Completion should be easy, but is left to you to do.