Author 
Topic: Seating Couples (Read 11890 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Seating Couples
« on: May 27^{th}, 2003, 6:28pm » 
Quote Modify

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 (18421891). Came up with the closedform 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.


IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



hyperdex
Newbie
Gender:
Posts: 2


Re: Seating Couples
« Reply #1 on: May 28^{th}, 2003, 12:55pm » 
Quote Modify

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 inclusionexclusion. 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 2N2K normal seats. In total, we have 2NK seats and we must choose K of them to be love seats. This can be done in C(2NK, 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 (NK)!^2 ways. This means that the total number of arrangements where the K husbands sit next to their wives is 2*C(2NK,K)*K!*(NK)!^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(2NK, K) * (NK)! and our desired answer would be this divided by 2N which is (N1)! \sum_{K=0}^{N} (1)^k * C(2NK, K) * (NK)! Unfortunately, I do not know if there is a closed form for this.

« Last Edit: May 28^{th}, 2003, 12:57pm by hyperdex » 
IP Logged 



Nigel_Parsons
Junior Member
Gender:
Posts: 63


Re: Seating Couples
« Reply #2 on: Apr 30^{th}, 2004, 5:21pm » 
Quote Modify

“A simple equation is a thing of beauty!” Finding this in the ‘Unsolved – Hard’ puzzles, I started from basics. :: 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 (N1) 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 (N2) men. By similar logic, the next woman can be chosen from (N2), and the next man from (N3) 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 (N1)*(N2)*(N3).....*1 It will be seen that the number of solutions for men is (N2)*(N3).....*1 This gives (N1)! * (N2)! 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 (N1). This reduces the possibilities to ((N1)! * (N2)!)/(N1) = (N2)! * (N2)! = ((N2)!)^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 (((N2)!)^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 ((((N2)!)^2)/2)/(N/2) = (((N2)!)^2)/N :: I’m not totally happy with my final paragraph, but I believe I’ve ‘broken the back’ of this question

« Last Edit: Apr 30^{th}, 2004, 5:23pm by Nigel_Parsons » 
IP Logged 



ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: Seating Couples
« Reply #3 on: May 1^{st}, 2004, 12:11pm » 
Quote Modify

Quote:So the final solution would be ((((N2)!)^2)/2)/(N/2) = (((N2)!)^2)/N 
 Putting N = 3 gives 1/3 ways.


IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



rmsgrey
Uberpuzzler
Gender:
Posts: 2818


Re: Seating Couples
« Reply #4 on: May 1^{st}, 2004, 2:59pm » 
Quote Modify

on Apr 30^{th}, 2004, 5:21pm, Nigel_Parsons wrote:By similar logic, the next woman can be chosen from (N2), and the next man from (N3) 
 At this stage you have (using capitals to denote men; lowercase women) AbC. The next woman could be any of n2, including a, in which case, with AbCa, the next man is one of n2 rather than the n3 for AbCd. In general, the number of possibilities for the next person increases by one when the previous person's spouse is already seated.


IP Logged 



ivancho
Newbie
Gender:
Posts: 3


Re: Seating Couples
« Reply #5 on: Oct 12^{th}, 2004, 5:59pm » 
Quote Modify

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}^{2Nk} * (Nk)! * 2N / (2N k) and you can multiply that by (N1)!, 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 (N1)! 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 inclusionexclusion, 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 i1. 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_{0} * N!  r_{1} * (N1)! + r_{2} * (N2)! ..., 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}^{2Nk} * 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 (2Nk)* r_{k}, counting them via placing the blue one first gives 2N * C_{k}^{2Nk}. 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..

« Last Edit: Oct 12^{th}, 2004, 6:25pm by ivancho » 
IP Logged 



