It's 8! minus all the unwanted seating arrangements:
So we have to calculate the number of unwanted seating arrangements
this way:
Let A = the unwanted case that couple 1 sits together.
Let B = the unwanted case that couple 2 sits together.
Let C = the unwanted case that couple 3 sits together.
Let D = the unwanted case that couple 4 sits together.
So we want N(A or B or C or D)
The "sieve" formula for the answer (sometimes called the "inclusion and
exclusion" formula is:
N(A or B or C or D) = N(A) + N(B) + N(C) + N(D)
- N(A&B) - N(A&C) - N(A&D) - N(B&C) - N(B&D) - N(C&D)
+ N(A&B&C) + N(A&B&D) + N(A&C&D) + N(B&C&D)
- N(A&B&C&D)
It's easy to see that:
N(A) = N(B) = N(C) = N(D)
N(A&B) = N(A&C) = N(A&D) = N(B&C) = N(B&D) = N(C&D)
N(A&B&C) = N(A&B&D) = N(A&C&D) = N(B&C&D)
So the "sieve" formula becomes
N(A or B or C or D) = 4N(A) - 6N(A*B) + 4N(A&B&C) - N(A&B&C&D)
We calculate N(A)
We will use (x,y) to mean that a couple sits in seats #x and #y
Choose couple 1's seats 7 ways: (1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8)
Choose the way they can sit 2! ways: (husband,wife) or (wife,husband)
Seat the other 6 people 6! ways.
That's 7×2!×6! = 10080
N(A&B) = 10080
We calculate N(A&B)
Couples 1 and 2 can use 4 seats in these 15 ways:
{(1,2),(3,4)}, {(1,2),(4,5)}, {(1,2),(5,6)}, {(1,2),(6,7)}, {(1,2),(7,8)},
{(2,3),(4,5)}, {(2,3),(5,6)}, {(2,3),(6,7)}, {(2,3),(7,8)}, {(3,4),(5,6)},
{(3,4),(6,7)}, {(3,4),(7,8)}, {(4,5),(6,7)}, {(4,5),(7,8)}, {(5,6),(7,8)}
Choose whether couple 1 is left of couple 2 or vice-versa in 2! ways:
Choose the way couple 1 can sit 2! ways: (husband,wife) or (wife,husband)
Choose the way couple 2 can sit 2! ways: (husband,wife) or (wife,husband)
Seat the remaining 4 people 4! ways.
That's 15×2!×2!×2!×4! = 2880 ways.
N(A&B) = 2880
We calculate N(A&B&C)
Couples 1, 2 and 3 can use 6 seats in these 10 ways:
{(1,2),(3,4),(5,6)}, {(1,2),(3,4),(6,7)}, {(1,2),(3,4),(7,8)},
{(1,2),(4,5),(6,7)}, {(1,2),(4,5),(7,8)}, {(1,2),(5,6),(7,8)},
{(2,3),(4,5),(6,7)}, {(2,3),(4,5),(7,8)}, {(2,3),(5,6),(7,8)},
{(3,4),(5,6),(7,8)}
We can choose the order of the 3 couples is 3! or 6 ways.
Choose the way couple 1 can sit 2! ways: (husband,wife) or (wife,husband)
Choose the way couple 2 can sit 2! ways: (husband,wife) or (wife,husband)
Choose the way couple 3 can sit 2! ways: (husband,wife) or (wife,husband)
Seat the remaining 2 people 2! ways.
That's 10×3!×2!×2!×2!×2! = 960 ways.
N(A&B&C) = 960
We calculate N(A&B&C&D)
(They use all 8 seats)
Choose the order of the 4 couples 4! = 24 ways
Choose the way couple 1 can sit 2! ways: (husband,wife) or (wife,husband)
Choose the way couple 2 can sit 2! ways: (husband,wife) or (wife,husband)
Choose the way couple 3 can sit 2! ways: (husband,wife) or (wife,husband)
Choose the way couple 4 can sit 2! ways: (husband,wife) or (wife,husband)
That's 4!×2!×2!×2!×2! = 384
Substitute in "sieve" formula to get the number of unwanted seating
arrangements:
N(A or B or C or D) = 4N(A) - 6N(A&B) + 4N(A&B&C) - N(A&B&C&D)
N(A or B or C or D) = 4(10080) - 6(2880) + 4(960) - 384 = 26496
Subtract from 8!:
8! - 26496 = 40320 - 26496 = 13824.
Answer: 13824
Edwin McCravy
[1,-1,2,-2,4,-4,8,-8].permutation.map{|p| [p[0..-2].zip(p[1..-1]).map{|t| t.inject(:+)}.inject(:*).abs, 1].min}.inject(:+)
, or try haskell:sum $ map (\p -> min 1 $ abs $ product $ map (uncurry (+)) $ zip p $ tail p) $ permutations [1,-1,2,-2,4,-4,8,-8]
$\ddot\smile$ $\endgroup$ – dtldarek Aug 8 '13 at 20:23