Results 1 to 3 of 3

Thread: Dividing 3n couples into triplets

  1. #1
    Junior Member gusztav's Avatar
    Joined
    Jan 2008
    Posts
    48
    Awards
    1

    Dividing 3n couples into triplets

    There are $\displaystyle 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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Let $\displaystyle a_n$ be the desired number and $\displaystyle b_n$ be the number of arrangements into triplets in which, in at least one triplet, there's a married couple. Then $\displaystyle a_n+b_n$ is the total number of arrangements of our 6n persons into triplets. That number is: $\displaystyle C=\binom{ 6n}{3 }\cdot \binom{ 6n-3}{3 }...\binom{ 3}{3 } $

    We have: $\displaystyle 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 $\displaystyle C_1$ ... $\displaystyle C_{3n}$ each couple is a set of 2 persons. ( they are disjoint)

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

    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,742
    Thanks
    2814
    Awards
    1
    Quote Originally Posted by PaulRS View Post
    Then $\displaystyle a_n+b_n$ is the total number of arrangements of our 6n persons into triplets. That number is: $\displaystyle C=\binom{ 6n}{3 }\cdot \binom{ 6n-3}{3 }...\binom{ 3}{3 } $
    Paul, your $\displaystyle C$ counts labeled partitions.
    Whereas, groups of three are not labeled. Therefore divide by $\displaystyle (2n)!$.
    Last edited by Plato; Jan 9th 2009 at 02:46 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. couples problem
    Posted in the Statistics Forum
    Replies: 4
    Last Post: Jan 20th 2011, 03:59 PM
  2. Triplets
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Feb 4th 2010, 02:33 AM
  3. Pythagorean Triplets
    Posted in the Number Theory Forum
    Replies: 8
    Last Post: Aug 5th 2009, 11:54 AM
  4. couples
    Posted in the Statistics Forum
    Replies: 3
    Last Post: Jan 10th 2008, 10:35 AM
  5. Given twenty couples...
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: Feb 1st 2007, 07:12 AM

Search Tags


/mathhelpforum @mathhelpforum