Couples

Five couples (one man, one woman) come into a restaurant and they all sit at at long rectangular table. They all only sit on the long sides, not the shorter sides. Each couple sits either directly across from each other, or right next to each other. How many ways can the couples be seated at the table?

(The table has 5 seats on each of the long sides, and each person must sit in one of those seats)


The answer is 30720.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Satyen Nabar
May 1, 2015

3 3 Scenarios

( A ) (A) Each of the 5 5 couples sit with partners facing each other. They can be seated in 5 ! = 120 5! = 120 ways. All can exchange seats with partner so that's 120 2 5 = 3840 120*2^5= 3840 ways.

( B ) (B) If one couple sits next to each other then there has to be another couple that sits across from them. The rest of the 3 3 couples sit with partners facing opposite each other. The 2 couples that sit next to each other across the table are selected in ( 5 2 ) = 10 \binom{5}{2}=10 ways. They can choose where to sit in 4 4 ways. The couples can exchange places in 2 2 ways. The other 3 3 couples can choose their places in 3 ! = 6 3!= 6 ways. Finally all of them can exchange places with partner in 2 5 2^5 ways so that's 10 4 2 6 2 5 = 15360 10*4*2*6*2^5= 15360 ways.

( C ) (C) If two couples sit next to each other side on one side of the table, two other couples must sit opposite them on the other side. The fifth couple then sits facing each other. The 4 4 couples can be chosen in ( 5 4 ) = 5 \binom{5}{4}=5 ways. They can choose their places in 3 3 ways. They can sit on those seats in 4 ! = 24 4!= 24 ways. All five couples can exchange seats with their partner in 2 5 2^5 ways. So its 5 3 24 2 5 = 11520 5*3*24*2^5=11520 ways.

Total of 3840 + 15360 + 11520 = 30720 3840+15360+11520= 30720 ways.

I get this wrong. I thought how many couples I see at the table. I get this all wrong, but it was fun. I would like to try it again.

Marijana Marinić-Kragić - 5 years, 9 months ago
Saurabh Khurana
Dec 9, 2016

||||| |||-- ||--| |--|| --||| |---- --|-- ----|

These are the 8 ways the couples can be seated. | represents a couple sitting facing each other. -- represents a couple right next to each other. For each of the 8 combinations above, we can fit the couples in 5! ways. Each of the 5 couples can be seated in 2 ways in their slot. So the total is 8.5!.2^5 = 30720.

That 8 happens to also be a Fibonacci number. Notably, it is impossible for two people from different couples to sit opposite one another without their partners also be opposite each other; that is, your | and -- are the only options.

Now with n couples the number of arrangements is the (n+1)st Fibonacci number:

With one couple, only | is possible.

With two couples there are two choices: || and --.

With k+1( 3 \geq3 ) couples, the last seats are either | or -; in the first case the remaining seats can be filled in F(k) ways, and in the latter the arrangement actually ends in --, and the remaining seats can be filled in F(k-1) ways; so the total number of ways is F(k)+F(k-1), and the Fibonacci recurrence is satisfied.

So we get the more general solution: for n couples, the number of arrangements is F n + 1 n ! 2 n F_{n+1}*n!*2^n

Ben Reiniger - 4 years, 5 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...