Eight couples meet up at a restaurant. What is the probability that no one sits next to their mate? (assume they sit in a row)
Before retiring I loved to teach combinatorics at a simple level to in service teachers. They need renewal credits and a collection of problems giving "real world" applications. This was one I used to work on the concept of
inclusion-exclusion. Say that the couples are named \(\displaystyle A,~B,~C~\&~D\).
In order to find the number of ways that none of these four couples sits together we must subtract the number of ways at least on of the couples sit together from the total possible arrangements \(\displaystyle 8!\). To find the of ways at least one couple is together we use inclusion/exclusion.
We add \(\displaystyle ||A||+||B||+||C||+||D||-||AB||-||AC||-||AD||-||BC||-||BD||-||CD||+||ABC||+||ABD||+||ACD||+||BCD||-||ABCD||\)
The couples taken on at a time minus two at a time plus three at a time and finally minus four at a time.
Now lets consider each of the four types.
\(\displaystyle ||A||=2\cdot 7!\) is the number of ways couple \(\displaystyle A\) can sit together. The 2 comes from the fact the wife can sit on either side of the husband.
Then that one unit along with the six others makes seven.
\(\displaystyle ||AB||=4\cdot 6!\) is the number of ways couples \(\displaystyle A~\&~B\) can each sit together, although the couples are not necessarily together.
\(\displaystyle ||ABC||=8\cdot 5!~\&~||ABCD||=16\cdot 4!\)
\(\displaystyle \displaystyle\sum\limits_{k = 0}^4 {{{( - 1)}^k}\left( {\begin{array}{*{20}{c}} 4\\ k \end{array}} \right)\left[ {{2^k}(8 - k)!} \right]} \) is the number of ways that none of the couples sits together.
To see the probability that no couple is together
SEE HERE
One can see how using a modified Mooore method, that can make a three hour night class.