Dividing 3n couples into triplets

**gusztav** · January 9th 2009, 08:02 AM

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!

**PaulRS** · January 9th 2009, 02:00 PM

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$

**Plato** · January 9th 2009, 02:33 PM

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)!$ .

Thread: Dividing 3n couples into triplets

LinkBack

Thread Tools

Display

Dividing 3n couples into triplets

Similar Math Help Forum Discussions

couples problem

Triplets

Pythagorean Triplets

couples

Given twenty couples...

Search Tags