How many arrangements are possible

1. Apr 26, 2005

Directrix

I'm stuck on the following question and I don't what to do,

At a banquet hall, four couples are sitting along one side of a table. How many arrangements are possible if no one is sitting beside his or her partner.

Any help appreciated.

2. Apr 27, 2005

BicycleTree

The only way I know how to do this is, take the total number of arrangements. Now subtract out the # of arrangements with at least couple 1 together (and maybe other couples together too), then subtract out the # of arrangements with at least couple 2 together (and maybe other couples together too) and subtract out the same for couples 3 and 4. Now you have some overlapping because when you have two couples together, you subtracted it twice (once for each couple). So you want to add that back in again; so add back the number of ways that you can have at least two couples together, for each possible combination of 2 couples. Now you have miscounted again: how many times have you counted so far the arrangements when you have 3 couples together? Now add or subtract back that number (and you'll have to use "at least" again) to get the right # of arrangements for 3 couples. Now consider 4 couples together, and again add or subtract appropriately to correct, and that's your answer.

3. Apr 27, 2005

Directrix

I think I have the right answer now,
8! - 7! x 2
= 30240

This assumes one couple is sitting together, but also includes arrangements when 2, 3, or all 4 couples sit together.

4. Apr 27, 2005

BicycleTree

No, though you're on the right track. You have subtracted the ways for one particular couple--say, couple 1--to sit together. You have not subtracted the ways for (for example) couple 2 to sit together when couple 1 is not sitting together.

If you do it by subtracting I think you pretty much have to do it the way I said. The first thing you'd be subtracting is 4 x 2 x 7!, subtracting once for each possible couple, and then you'd add back in to correct, and so on.

5. Apr 28, 2005

Directrix

Ok, yes you're right. The only thing that troubles me is that 2 x 4 x 7! = 8!, am I heading the right way by doing the following?
8! - 7! x 2 - 6! x 4 - 5! x 8 - 4! x 16
= 26016
I'm not sure how many to add (because some do overlap), could someone maybe explain how I would find the number of overlapping cases?

6. Apr 29, 2005

LittleWolf

This is a typical inclusion/exclusion problem. Consider one couple sitting together as a unit then you have 2*7! permutations. Two couples have 4*6! permutations. Three couples have 8*5! permutations. Four couples have 16*4! permutations. The number of arrangements should be 8!-[C(4,1)*2*7!-C(4,2)*4*6!+C(4,3)*8*5!-C(4,4)*16*4!] where the number inside the [] is the number of arrangements where at least one couples is sitting together.So 8!-[] is no couple sitting together.

7. Apr 29, 2005

BicycleTree

Hmm, littlewolf--with you until you got to " - C(4,4)*16*4!." I'm reasoning that it might be " + 7*C(4,4)*16*4!." I'll write a program to find out later.

8. Apr 29, 2005

AKG

I tried working it out by cases. It didn't take too long, just drew a little tree diagram, and the answer I'm getting is 14976. I'd have to think some more to figure out a way to generalize it, but this method only took 5 minutes or so, so you can see try solving it by cases and see if you like that approach.

9. Apr 29, 2005

BicycleTree

Ah, I had just dropped a minus sign. You're right LittleWolf.

10. Apr 30, 2005

gptejms

This can't be right:-you are subtracting C(4,1)*2*7! which equals 8! from 8! in the first go and then subtracting further! I think the right way is the following:-
From 8! you subtract the permutations for the following cases:-
1.All 4 H's(husbands)are seated with their W's(wives).
2.Any 3 H's are seated with their W's,the remaing H doesen't sit with his W.
3. Any 2 H's are seated with their W's,the remaining two H's do not sit with their respective W's.
4.Any one H is seated with his W,the rest of the H's don't sit with their respective W's.
Figure out the permutations for the above 4 cases and subtract from 8!

11. Apr 30, 2005

BicycleTree

gptejms, he is right and your way would be very difficult to calculate.

12. Apr 30, 2005

LittleWolf

gptejms, check the two cases of only one couple at the table and only two couples at the table. One couple at the table: 2!-[C(1,1)*2*1!]=0. Two couples at the table: 4!-[C(2,1)*2*3!-C(2,2)*4*2!]=8.

13. May 1, 2005

gptejms

Ok,I didn't note that LittleWolf was not just subtracting (from 8! ) but also adding to it.The way I suggested is also doable though it's a bit longer.

14. May 4, 2005

Directrix

Thank you for all your replies! This solves my problem.

Last edited: May 4, 2005