There are $8$ chairs in $2$ rows one behind the other. $4$ couples are to be seated on these chairs. while arranging them we found that no husband is sitting in front or behind his wife. The total such arrangements are $C(8,4)\times k$. Find $k$.
I am trying to solve it by making cases.
Case I : When no couple occupies same row
So we will select one each from $4$ couples in $16$ ways and then arrange them in $4!$ ways and in second row we do derangement of $4$ people. So the answer from case $\mathbf{Case\;I}$ is
$$16\cdot4!\cdot9$$
Case II : $2$ couples occupy same row
In this case we choose $2$ couples in $C(4,2)$ ways and arrange them in $4!$ ways and arrangement remaining $4$ in second row. So the answer from case $\mathbf{Case\;II}$ is
$$C(4,2)\cdot4!\cdot4!$$
Case III : When each row contains exactly one couple
This is the case which I am not able to calculate.
Could someone help me with case or suggest an alternate and more efficient approach to tackle this problem?
Best Answer
I will not repeat what you have already done in case $1$ and $2$. They are correct. Coming to case $3$, when front row seats exactly one couple (and so the other row will seat exactly one couple as well).
There are $4$ ways to choose a couple for the front row.
Number of ways to choose rest two for the front row is,
$\displaystyle {6 \choose 2} - {3 \choose 1} = 12$
That is to choose $2$ people from remaining $6$ people but subtracting number of ways of having chosen a couple.
Now we need to ensure that none of the two in the back row who are not couple are seated behind their spouses.
For every arrangement of front row, number of arrangements in the back row are -
Number of arrangements where both are seated behind their spouses is $2$ (as couple seating in the back row can swap places).
Number of arrangements where exactly one of them is seated behind their spouses is $2 \cdot 2 \cdot 2 = 8$ (once one of the non-couple is seated behind spouse, the other non-couple has $2$ places to choose from, except the place behind spouse and then like before, couple in the back row can be seated in remaining two places in $2$ ways).
So favorable arrangements are $4! - (2 + 8) = 14$
Or simply by Principle of Inclusion Exclusion, $4! - 2 \cdot 3! + 2! = 14$
So number of arrangements for Case $3$ is,
$\displaystyle 4 \cdot 12 \cdot 4! \cdot 14 = 16128$
Total number of arrangements is $2 \cdot 3456 + 16128 = 23040$.