Q. Three couples sit for a photograph in 2 rows of three people each such that no couple is sitting in
the same row next to each other or in the same column one behind the order. How many
arrangements are possible?
_ _ _
_ _ _
I used inclusion-exclusion for this. Let couples be $A_1B_1$, $A_2B_2$, $A_3B_3$. Let the sets be defined as –
$S_1$ = Cases in which at least 1 couple is in the same row, directly adjacent each other.
$S_2$ = Cases in which at least 1 couple is in the same column.
Total cases = $6!$
$n(S_1)$ = $4 \times 3 \times 2 \times 4!$.
Here 4 = Choosing of 2 horizontally-adjacent places, 3 = Three pairs of couples, 2 = Permutations of the horizontally-adjacent couple, 4! = No. of ways to arrange remaining 2 couples.
$n(S_2)$ = $3 \times 3 \times 2 \times 4!$.
Here 3 = Choosing of 2 vertically-adjacent places, 3 = Three pairs of couples, 2 = Permutations of the vertically-adjacent couple, 4! = No. of ways to arrange remaining 2 couples.
$n(S_1 ∩ S_2)$ = $3C2 \times 4 \times 1 \times 2! \times 2! \times 2!$.
Here $3C2$ = Choosing of two pairs of couples, 4 = Choosing of 2 horizontally-adjacent places, 1 = Forced selection of vertically-adjacent place, $2!,2!,2!$ = Permutations of horizontally-adjacent, vertically-adjacent, remaining two respectively.
However it seems like $S_1∪ S_2$ is coming out to be greater than the universal set(total cases). I'm guessing I made some error in counting, or maybe in taking the sets. Help.
Best Answer
There are easier ways to handle this, as other answers have suggested. However, I will provide an answer using the Inclusion-Exclusion principle.
There are a total of $6! = 720$ total arrangements for the rows and columns to be filled out. Now let $$S_i := \text{couple } (A_i,B_i) \text{ are seating adjacent to each other}.$$ Notice that this could mean that the couples are sitting row-wise or column-wise adjacent. Now, to find the number of ways where no couples are adjacent, we will first find the number of ways in which at least one couple is seated adjacent to each other.
Using Inclusion-Exclusion, we are looking for $$|S_1 \cup S_2 \cup S_3| = |S_1| + |S_2| + |S_3| - |S_1 \cap S_2| - |S_2 \cap S_3| - |S_1 \cap S_3| + |S_1 \cap S_2 \cap S_3|.$$
Let's break it down.
Finding $|S_1|$. The general strategy is to sit down $C_1$ first. There are $7$ ways to find adjacent seats for $C_1$. For each of these cases, 4 seats remain empty and can be occupied in $4!$ ways. Now, since the couple $C_1$ can permute within their seats, we need to multiply by $2$, yielding a total of $$|S_1| = 7 \times 2 \times 4! = 336.$$ Notice that, by symmetry, $|S_1| = |S_2| = |S_3| = 336.$
Finding $|S_1 \cap S_2|$. Again, let $C_1$ sit first, followed by $C_2$. Here we consider different subcases.
$C_1$ are row-wise adjacent.There are $4$ ways in which $C_1$ can pick adjacent row-wise seats. For each of these cases, there are $3$ choices for $C_2$ to sit adjacent to each other. Remember $C_1$ and $C_2$ can permute within their seats, so multiply by $2\times2$. Finally, there are $2$ seats for the remaining couple, bringing the total to $$4 \times 3 \times 2 \times 2 = 96.$$
$C_1$ are column-adjacent in one of the edges. There are two ways to do this, and for each of these there are $4$ choices for $C_2$ to be adjacent and $2$ seats for the rest. Remembering to adjust by permutations within $C_1$ and $C_2$ we get a total of $$2 \times 4 \times 2 \times 2 \times 2 = 64. $$
$C_1$ sit column-adjacent in the middle seats. In this case, there are $2$ choices for $C_2$ to sit adjacent to each other. The other couple has $2$ ways to sit down. Remembering permutations within $C_1$ and $C_2$, this brings us to a total of $$1 \times 2 \times 2 \times 2 \times 2 = 16.$$
Putting it together, $$|S_1 \cap S_2| = 96+64+16 = 176.$$ Remember that, by symmetry, $|S_1 \cap S_2| = |S_1 \cap S_3| = |S_2 \cap S_3|$. Almost there.
Finding $|S_1 \cap S_2 \cap S_3|.$ Here we can use other cases.
$C_1,C_1,C_3$ are all column-adjacent. We can view them as blocks, and perform a permutation of them, yielding $3! = 6$. Remembering the permutation within each couple, we need to multiply by $2 \times 2 \times 2 = 8$, yielding a total of $6 \times 8 = 48$ ways for this to happen.
One of the couples $C_i$ is vertically adjacent. We can pick which couple in $3$ ways. We can pick one of the edges in $2$ ways.The 2 couples can be seen as row-adjacent blocks, and we can seat them in $2$ ways. Remembering to adjust by permutation within the couples, this yields a total of $$3 \times 2 \times 2 \times 2 \times 2 \times 2 = 96.$$
Putting it together, $$|S_1 \cap S_2 \cap S_3| = 48 + 96 = 144.$$
Returning to the original equation, we can now substitute to obtain:
$$|S_1 \cup S_2 \cup S_3| = 3 \times 336 - 3 \times 176 + 144 =624.$$
Then, the number of ways so that no rows or columns are couple-adjacent is found by $720-624 = 96.$