wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Seating Couples
        
(Message started by: william wu on May 27^th, 2003, 6:28pm)

Title: Seating Couples
Post by william wu on May 27^th, 2003, 6:28pm

N married couples are to be a seated at a round table. Two arrangements are considered identical if one is a rotation of the other. In how many different arrangments can n married couples be seated such that there is always one man between two women, and none of the men is ever next to his own wife?

Source: Edouard Lucas (1842-1891). Came up with the closed-form formula for Fibonacci numbers and the Tower of Hanoi puzzle. Died of a freak accident at a banquet, when a plate fell and a shard flew into his cheek.

Title: Re: Seating Couples
Post by hyperdex on May 28^th, 2003, 12:55pm

Here's a partial solution...

First, we will count the total number of arrangements that satisfy the alternating condition with no man seated next to his wife. Dividing this result by 2N will produce the desired answer.

We will use the principle of inclusion-exclusion. Given K<=N, how many arrangements are there so that a fixed set of K husbands are seated next to their wives?

Designate one chair to be the "head" and let's first solve the K=0 case. The head will contain either a male or a female, and once this decision has been made there are (N!)^2 possible arrangements. This means that in total there are 2(N!)^2 arrangements for K=0.

Suppose K>0 and fix a set of K husbands. As before, we decide in advance whether the head seat has a man or a woman. Consider a round table where we will have K love seats that will seat a husband and his wife and 2N-2K normal seats. In total, we have 2N-K seats and we must choose K of them to be love seats. This can be done in C(2N-K, K) ways. Once we have chosen the love seats we can arrange the K husband/wife combos in exactly K! ways. Once they are fixed, we can arrange the remaining husbands and wives in (N-K)!^2 ways. This means that the total number of arrangements where the K husbands sit next to their wives is 2*C(2N-K,K)*K!*(N-K)!^2. Call this number F(N, K).

The principle of inclusion/exclusion implies that the total number of arrangements where no husband is seated next to his wife is exactly

\sum_{K=0}^{N} (-1)^k * C(N, K) * F(N, K)

Using the formula for F(N, K), this can be "simplified" to

2(N!) \sum_{K=0}^{N} (-1)^k * C(2N-K, K) * (N-K)!

and our desired answer would be this divided by 2N which is

(N-1)! \sum_{K=0}^{N} (-1)^k * C(2N-K, K) * (N-K)!

Unfortunately, I do not know if there is a closed form for this.

Title: Re: Seating Couples
Post by Nigel_Parsons on Apr 30^th, 2004, 5:21pm

“A simple equation is a thing of beauty!”

Finding this in the ‘Unsolved – Hard’ puzzles, I started from basics.
:: [HIDE]
For N couples (N>2: N=2 is impossible of solution)

Position first man, (Mr A) at a set point at the table. This avoids any duplication due to rotation, as we are looking at all seating plans relative to Mr A.

Set a woman (Mrs B) in the seat to his immediate left. This must not be Mrs A, so can be any one of (N-1) women.
At the next seat, place Mr C. As he is neither Mr A, nor the husband of Mrs B, he can be any one of (N-2) men.
By similar logic, the next woman can be chosen from (N-2), and the next man from (N-3)
This continues until all the seats are filled. The last two people to be seated are the Nth man, and the Nth woman. So for these there is no choice.

It will be seen that the number of solutions for women is (N-1)*(N-2)*(N-3).....*1
It will be seen that the number of solutions for men is (N-2)*(N-3).....*1
This gives (N-1)! * (N-2)! Possibilities.

However, the seating plan will fail if Mrs A is the last woman to be seated. As we deliberately avoided seating her to the left of her partner, the chance of her being the last to be seated is 1 in (N-1).
This reduces the possibilities to ((N-1)! * (N-2)!)/(N-1) = (N-2)! * (N-2)! = ((N-2)!)^2

Although rotations have been avoided, the mirror images have been included (where Mrs B sits to right of Mr A) and these would give everyone the same two partners only on opposite sides. Depending on how the question is phrased, the required answer may be (((N-2)!)^2)/2

The seating plan will also fail if the last man to be seated is the partner of either of the remaining ladies.
This is a chance of N/2. So the final solution would be ((((N-2)!)^2)/2)/(N/2) = (((N-2)!)^2)/N [/HIDE] ::

I’m not totally happy with my final paragraph, but I believe I’ve ‘broken the back’ of this question

Title: Re: Seating Couples
Post by THUDandBLUNDER on May 1^st, 2004, 12:11pm

Quote:

So the final solution would be ((((N-2)!)^2)/2)/(N/2) = (((N-2)!)^2)/N

Putting N = 3 gives 1/3 ways. ???

Title: Re: Seating Couples
Post by rmsgrey on May 1^st, 2004, 2:59pm

on 04/30/04 at 17:21:50, Nigel_Parsons wrote:

By similar logic, the next woman can be chosen from (N-2), and the next man from (N-3)

At this stage you have (using capitals to denote men; lower-case women) AbC. The next woman could be any of n-2, including a, in which case, with AbCa, the next man is one of n-2 rather than the n-3 for AbCd.

In general, the number of possibilities for the next person increases by one when the previous person's spouse is already seated.

Title: Re: Seating Couples
Post by ivancho on Oct 12^th, 2004, 5:59pm

I think Hyperdex' formula is slightly off - due to somehow counting mirror images in, or something like that. What I get is:
[smiley=sum.gif](-1)^k * C_k^2N-k * (N-k)! * 2N / (2N -k)
and you can multiply that by (N-1)!, if you want.

Let's say man number 1 always sits at the head chair, since we can rotate the table. In fact, let's have men 2, 3, 4... sit clockwise from him, leaving chairs between them for the wives. This will remove the above (N-1)! from the formula - if you want to count all other possible seatings of the men, just permute them, together with the wives, and you'll get that factor.

Now, rook polynomials are effectively inclusion-exclusion, but they generally represent the things to count in a better light. The numbers of the wives to the left of each man describe a permutation [smiley=pi.gif] of (1,2,..N), such that [smiley=pi.gif](i) is never equal to i or i-1. In terms of a rook configuration ( ie, N rooks on a NxN board, no 2 hitting each other ), it needs to be a configuration that avoids the main diagonal, upper second diagonal and a bottom left square. The main rook theorem tells us that the number of those configurations is r₀ * N! - r₁ * (N-1)! + r₂ * (N-2)! -..., where r_k is the number of ways to place k rooks on the avoided area so that no 2 hit each other. But on our forbidden area, the only way 2 rooks can threaten each other is if they are neighbours ( if you count the bottom left cell as neighbour of top left and bottom right). So r_k is equal to the number of ways we can choose k out of 2N marbles on a ring so that no 2 are neighbours. That number is C_k^2N-k * 2N / (2N - k) - I suppose here it's the same thing as Hyperdex's solution, where we can't have the left side of a love seat be a neighbour of another left side.. I think the easiest way to derive the number itself is to count something slightly different - ie, k red and 1 blue marbles, so that no 2 red are adjacent - counting those placing red ones first gives (2N-k)* r_k, counting them via placing the blue one first gives 2N * C_k^2N-k. And that's that..

I think this is the most closed form we can get. Apparently it's possible to get a recurrence relation, but I haven't bothered with that..

Title: Re: Seating Couples
Post by nakli on Jul 19^th, 2012, 6:33am

http://en.wikipedia.org/wiki/M%C3%A9nage_problem