# Dividing 3n couples into triplets

• Jan 9th 2009, 09:02 AM
gusztav
Dividing 3n couples into triplets
There are $3n$ married couples. In how many ways can they be arranged into triplets, if in each triplet, there must not be a married couple ?

I should solve this using the Principle of Inclusion-Exclusion, but don't really know where to start and how to solve this problem. I'd be very grateful for any help!
• Jan 9th 2009, 03:00 PM
PaulRS
Let $a_n$ be the desired number and $b_n$ be the number of arrangements into triplets in which, in at least one triplet, there's a married couple. Then $a_n+b_n$ is the total number of arrangements of our 6n persons into triplets. That number is: $C=\binom{ 6n}{3 }\cdot \binom{ 6n-3}{3 }...\binom{ 3}{3 }$

We have: $C =\frac{ (6n)!}{3!\cdot (6n-3)! }\frac{ (6n-3)!}{3!\cdot (6n-6)! }...=\frac{(6n)! }{ 6^{2n} }$

Let's name the married couples as $C_1$ ... $C_{3n}$ each couple is a set of 2 persons. ( they are disjoint)

Consider now $P_k$ to be the set of all arrangements of the 3n couples into triplets such that $C_k$ is included in one triplet. Then the union of $P_1$ ... $P_{3n}$ is $b_n$. Do that by using Inclusion-Exclusion and then remember that $a_n=C-b_n$

(Wink)
• Jan 9th 2009, 03:33 PM
Plato
Quote:

Originally Posted by PaulRS
Then $a_n+b_n$ is the total number of arrangements of our 6n persons into triplets. That number is: $C=\binom{ 6n}{3 }\cdot \binom{ 6n-3}{3 }...\binom{ 3}{3 }$

Paul, your $C$ counts labeled partitions.
Whereas, groups of three are not labeled. Therefore divide by $(2n)!$.