1

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!

ram
  • 11
  • Why isn't HW HHWW valid? Is H HW HW W valid? If you just forgot those, have you heard about Catalan numbers? – Arthur Aug 20 '16 at 11:35
  • Have you calculated this for small N like 2,3,4? – iamvegan Aug 20 '16 at 11:36
  • In your second example, if I am indexing it correctly, you have $H_1 H_2 W_2 W_1 H_3 W_3$. It looks like $H_2$ and $W_2$ are not seating together nor between some other couple. Doesn't this violate the conditions you gave? – iamvegan Aug 20 '16 at 11:44
  • yeah H HW HW W is valid. i have mentioned just 3 of the 5 possible cases @Arthur – ram Aug 20 '16 at 12:06
  • for 4 couples i got 12 possible arrangements. But i am not sure it's correct or not? @iamvegan – ram Aug 20 '16 at 12:07
  • Then as @Arthur said this is indeed Catalan numbers. Please check the link he gave. – iamvegan Aug 20 '16 at 12:11

1 Answers1

1

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!$

true blue anil
  • 41,295