There are $n$ couples, so $2n$ people in total. There are $n$ chairs in a row and behind the chairs there are $n$ standing places. All $2n$ want to have a group photo.
The condition for the group photo:
- EITHER a couple is next to each other
- OR a couple is in front of each other
Important: do not differentiate between male and female in a couple. So male-female and female-male counts as one combination.
I want to have a recursion, say $a(n)$, that gives the number of combinations for the group photo.
My attempt:
For $n=1$ it is trivial, we have $a(1) = 1$ combination.
For $n=2$ there are $a(2) = 2$ combinations. Let { _ _ , _ _ } = { standing row , chairs } be the matrix that represents the picture. Then these two are allowed: { a a , b b } and { a b , a b }. ({ a b , b a } is not allowed, since the conditions are not satisfied)
For $n=3$ I am unsure about my number. I have $a(3)=12$. Let a be constant, then we get these four matrices: { a b c , a b c } or { a c b , a c b } or { a b b , a c c } or { a c c , a b b }. In total that makes $3*4$ combinations, since on place of a we can get b and c, too.
So, we have $a(1) = 1$, $a(2) = 2$ and $a(3) = 12$. How do I get the recursion?
I am unsure about $a(3) = 12$, maybe this is wrong. Really appreciate your help!
Let $A_n$ be the number of arrangements, and take $n \ge 3$. Consider the leftmost chair. Then there's two options: (i) there's a couple such that one of the people stands behind it, and the other sits on it, or (ii) a couple sits on the chair and the one next to it.
In the first case, the couple does not interact with the remaining arrangement of chairs, so the situation devolves to a) choosing which pair stands across, and then b) choosing an arrangement of the remaining $n-1$ couples across the $n-1$ chairs. So, this case contributes $n A_{n-1}$ possibilities.
In the second case, notice that if the couple sits on the two leftmost chairs, another couple must stand behind them: since if the people standing behind were not a couple, the person standing behind the leftmost chair is separated from their partner. Once we pick these two couples, the remaining $n-2$ positions don't interact with them, and so this choice devolves to a) pick two couples, b) pick who stands and who sits, and c) pick an arrangement of the remaining $n-2$ chairs, leading to $n(n-1)A_{n-2}$ possibilities.
By inspection, we know that $A_1 = 1,$ and $A_2 = 4,$ and not 2: either a different couple occupies each position, which happens in two ways due to permuting the couples, or one couple occupies the chairs and the other stands behind, again yielding two ways due to the permutations (in the question you miss out $\{b b, aa\}$ and $\{ba,ba\}$, which are usually considered different from $\{aa,bb\}, \{ab,ab\}$ when placed in a row.).
So we have the recurrence $$ A_n = n A_{n-1} + n(n-1)A_{n-2}: n\ge 2; A_1 = 1, A_4 = 4. $$
This turns out to be easy to solve: if we define $B_n = A_n/n!,$ then the recurrence for $B_n$ satisfies $$ B_n = B_{n-1} + B_{n-2} : n\ge 2; B_1 = 1, B_2 = 2,$$ and so the $B_n$ are simply the Fibbonaci numbers, and $A_n = n! F_n,$ with the convention $F_1 = 1, F_2 = 2$.