3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ To the OP (i.e. original poster) : after reviewing the Inclusion-Exclusion oriented answer of Bergson, see this article for an introduction to Inclusion-Exclusion. Then, see this answer for an explanation of and justification for the Inclusion-Exclusion formula. $\endgroup$ Aug 27, 2023 at 16:18
  • $\begingroup$ @user2661923 alright, thanks $\endgroup$
    – acelixis
    Aug 27, 2023 at 17:54

4 Answers 4

5
$\begingroup$

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.

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

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

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

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

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

$\endgroup$
5
  • 4
    $\begingroup$ +1 : Very nice response, that provides good education to the OP (i.e. original poster) on the use of Inclusion-Exclusion. $\endgroup$ Aug 27, 2023 at 16:16
  • $\begingroup$ +1 for this nice answer $\endgroup$
    – TShiong
    Aug 28, 2023 at 14:12
  • $\begingroup$ In finding $|S1 ∩ S2 ∩ S3|$(case $2$), can you please explain what "The $2$ couples can be seen as row-adjacent blocks" means? $\endgroup$
    – acelixis
    Aug 31, 2023 at 1:30
  • 1
    $\begingroup$ @acelixis In case 2, only one of the couples should be column-wise adjacent. If we want the remaining 2 couples to be adjacent, but not column-wise (as then it's case 1), they are going to have to be row-wise adjacent. Since we know that they are going to be row-wise adjacent, we can just think of each couple as a block. So, instead of arranging 4 people into 4 seats, we take a couple as a unit, and the remaining spots in each row as a unit. Thus, we need to find a way to sit two couples (two units) in two spaces (each space consisting of two row-adjacent seats). $\endgroup$
    – Bergson
    Aug 31, 2023 at 9:27
  • 1
    $\begingroup$ @acelixis In essence, if you want to count how many ways of arranging objects there are, but you know that some of them always have to be adjacent, you can consider them as one block. E.g., if you want to arrange $5$ strangers in a line, you can view it as permuting the elements $p_1, p_2,p_3,p_4,p_5$. There are $5!$ for doing so. However, if you know $p_1$,$p_2$ and $p_3$ always sit together, you can call them $b_1$ and find the ways of permuting $b_1,p_4,p_5$. This yields $3! \times 3!$ (3 objects and there are 3! permutations within the block). This way, you know they always stay together. $\endgroup$
    – Bergson
    Aug 31, 2023 at 9:38
4
$\begingroup$

You're overcounting many cases. For instance the pattern $$\begin{array}{ccc} A_1&B_1&A_2\\A_3&B_3&B_2\end{array}$$ gets counted three times (once for $A_1, B_1$ sitting next to each other; once for $A_3, B_3$ sitting next to each other; and once for $A_2, B_2$ sitting one behind the other).

Suggestion (which doesn't use inclusion/exclusion): Select someone for front row center; then place their partner. Then select someone for the back row center; then place their partner. Then finish up.

$\endgroup$
3
$\begingroup$

Number the $6$ spots as
$B1\;B2\;B3$
$A1\;A2\;A3$

A little thought will show that to get a valid configuration, some couple must use a main diagonal, viz $A1B3$ or $A3B1$

and for each such placement, the remaining two couples have to be placed parallel to each other,crossing the main diagonal, eg for $A1B3$ the other two must be placed $A2B1$ and $A3B2$, thus choices with $A1B3$ used will be $3\cdot2\cdot1\times2^3 = 48$
(couples placed $\times$ persons occupying $A$ row)

Similarly for $A3B1$ main diagonal, gives answer $= 96$

$\endgroup$
1
$\begingroup$

Essentially, this answer is the same as true blue anil one, but from a different POV.

A few thoughts about possible arrangements shows that to get a valid one, we need to put exactly one person from each pair in each row (i.e., put the partners in different rows).

Consider the pairs $A$, $B$, and $C$. There are a total of $3!$ arrangements for them in the first row, and once the first row is selected, there are only $2$ valid arrangements for the second row (given the second constraint).
This results in a total of $3! \times 2$ arrangements for the pairs.

Finally, we have $2$ possible arrangements for people in each pair, resulting in a total of $2^3$ for all pairs.
The answer is $3! \times 2 \times 2^3 = 96$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .