How many arrangements are possible

  • Thread starter Directrix
  • Start date
In summary: I meant to subtract the total number of possible combinations of 1 couple at the table and 2 couples at the table- not just the number of arrangements with at least 1 couple at the table and 2 couples at the table.In summary, 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?
  • #1
Directrix
4
0
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.
 
Physics news on Phys.org
  • #2
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
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.
 
  • #4
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.
 
  • #5
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
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
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
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
Ah, I had just dropped a minus sign. You're right LittleWolf.
 
  • #10
LittleWolf said:
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!
 
  • #11
gptejms, he is right and your way would be very difficult to calculate.
 
  • #12
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
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
Thank you for all your replies! This solves my problem.
 
Last edited:

Related to How many arrangements are possible

1. How do you calculate the number of possible arrangements?

The number of possible arrangements can be calculated using the formula n! (n factorial), where n is the number of items being arranged. For example, if you have 5 items, there are 5! = 5 x 4 x 3 x 2 x 1 = 120 possible arrangements.

2. Do the arrangements have to be in a specific order?

Yes, the arrangements must be in a specific order for the calculation to be accurate. For example, the arrangements "ABC" and "ACB" are considered different arrangements because the order of the items is different.

3. Can repetitions be included in the arrangements?

Yes, repetitions can be included in the arrangements. For example, if you have 3 items and can repeat each item 3 times, there are 3 x 3 x 3 = 27 possible arrangements.

4. How does the number of items affect the number of possible arrangements?

The number of possible arrangements increases exponentially as the number of items increases. For example, if you have 10 items, there are 10! = 3,628,800 possible arrangements.

5. Can the number of possible arrangements be infinite?

No, the number of possible arrangements is finite and can be calculated using the formula n! where n is a positive integer. However, for large numbers, the number of possible arrangements can become so large that it is practically impossible to calculate or list out all of them.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
724
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
536
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
10K
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
6K
  • Quantum Interpretations and Foundations
2
Replies
37
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
2K
  • Astronomy and Astrophysics
Replies
6
Views
2K
Back
Top