0
$\begingroup$

In how many ways can we split 8 people who are married into 4 (unlabeled) groups of two (each group consists of one man and one woman) such that no group is a married couple? So a solution is a set $\{(M_1,W_1),(M_2,W_2),(M_3,W_3),(M_4,W_4)\}$. Hint: for $i=1,2,3,4$, let $A_i$ be the set of groupings $\{(M_1,W_1),(M_2,W_2),(M_3,W_3),(M_4,W_4)\}$ such that married couple $i$ is one of the groups.

$\endgroup$
  • 4
    $\begingroup$ Hint: look up "derangements". $\endgroup$ – Gerry Myerson Sep 21 '18 at 7:05
2
$\begingroup$

Let $A_i=\{\text{set of groupings such that married couple }i\text{, for $i=1,2,3,4$ is one of the groups}\}$ and $X=\{\text{# of ways to split 4 married couples in groups of 2 with one man and one woman}\}$. We know that $|X|=4!$ because if we first fix the 4 men, then there are 4! ways of seating the 4 women. For each $A_i$, there are $\left(\begin{array}{c} 4 \\ 1 \end{array}\right)$ ways to fix one married couple and then 3! ways to seat the remaining 3 women. Then the intersection of any two $A_i$'s would be $\left(\begin{array}{c} 4 \\ 2 \end{array}\right)$ ways to fix two married couples with 2! ways to seat the remaining 2 women. Similarly, for the intersection of three $A_i$'s, we get $\left(\begin{array}{c} 4 \\ 3 \end{array}\right)1!$ and the intersection of all 4 $A_i$'s would be $\left(\begin{array}{c} 4 \\ 4 \end{array}\right)0!$. By PIE, we have \begin{align*} |X\backslash(A_1\cup A_2\cup A_3\cup A_4)|=&4!-3!\left(\begin{array}{c} 4 \\ 1 \end{array}\right)+2!\left(\begin{array}{c} 4 \\ 2 \end{array}\right)-1!\left(\begin{array}{c} 4 \\ 3 \end{array}\right)+0!\left(\begin{array}{c} 4 \\ 4 \end{array}\right)\\ =&24-24+12-4+1\\ =&9. \end{align*}

Hence there are 9 ways we can split 8 people who are married into 4 (unlabeled) groups of two (each group consists of one man and one woman) such that no group is a married couple.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.