At a wedding party, 'N' couples are invited. A seating arrangement plan has to be formed for them. The problem is, couples either want to seat husband and wife together, or couples can sit between the husband and wife of another couple. Also, people will start seating from the left, and a wife will only take a seat after her husband has taken a seat. So a wife cannot seat on the left of her husband.
For example, if three couples are invited, then they can sit as
HHHWWW HHWWHW HWHWHW
Given n number of couples, I need to find the number of possible seating arrangements. I am stuck, please help me!
Here is a solution for $3$ couples.
Each couple is treated as one $HW$ entity, and the condition that "couples can sit between the husband and wife of another couple" is taken care of in the diagrams by nesting.
$\square\;\square\;\square = HWHWHW \to 3!$
$\boxed\square\;\square = HHWWHW \to 3!$
$\square\;\boxed{\square} = HWHHWW \to 3!$
$\boxed{\square\;\square} = HHWWHW \to 3!$
$\boxed{\boxed{\square}} = HHHWWW \to 3!$
Adding up, we get $5\times 3!$
After some thought, I see that the patterns correspond to counting $n$ pairs of correctly matched parentheses, which is one interpretation of the Catalan numbers
hence ans for $n$ pairs will be $C_n \times n!$