How many arrangements are possible

[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.

 

[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.

 

[Directrix]

Thank you for your reply.
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.

 

[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 into correct, and so on.

 

[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?

 

[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.

 

[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.

 

[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.

 

[BicycleTree]

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

 

[gptejms]

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.

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

 

[BicycleTree]

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

 

[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.

 

[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.

 

[Directrix]

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