0
$\begingroup$

Hi,

My question is : is there a known method to count how many couple can we make out of $2n$ three members family ?

To be more precise, let's say that we have $6n$ individuals grouped three by three in families and we want to count how many ways there are to make couples out of them, such that,

  1. No couple are made out of two members of the same familly.
  2. Sex is irrelevant (there's no sex, or we don't care about that : it's a math problem).
  3. Every individual belongs to one and only one couple.

I've found this problem very hard to say the least. Maybe some version of the Wick theorem or the combinatorial theory of Hermite polynomials can help solveing it.

An answer where the individuals are initially indistinguishable (unlabeled enumeration) is highly preferred but any answer will be appreciated. Counting those coupling is in my humble opinion much easier if one consider that the individuals are numbered from $1$ to $6n$

I have an answer (both labeled and unlabeled) to count those couplings by generating functions without assumption 1. above. But I can't find a way to incorporate that condition.
p.s : this is my first post here.

Improve this question
$\endgroup$
7
  • $\begingroup$ One method that sometimes works for this kind of problem is to solve the first few cases and then look up the results in the Online Encyclopedia of Integer Sequences. $\endgroup$
    – Gerry Myerson
    Commented Jan 30, 2012 at 22:10
  • $\begingroup$ If I understand correctly, these are essentially trivalent (cubic) graphs. Is oeis.org/A005638 what you're looking for? $\endgroup$
    – Ira Gessel
    Commented Jan 31, 2012 at 0:14
  • $\begingroup$ Thx for the references, this is very nice of you. This is exactly my problem. most of the references I've found googling cubic graphs, involves algorithms in the enumeration, not generating function (or Species) formulae. I'm gonna search harder. I'll post a link to my solution (which uses generating function and species) once I'm done writing the latex. I'm still unable to cope with condition 1. ^^. Maybe a combinatorial theory of Laplace transform can help. Does anyone knows of such result ? I think combinatorial convolution will be a first subject to look at. Tanks again. $\endgroup$
    – Samuel Vidal
    Commented Jan 31, 2012 at 19:06
  • $\begingroup$ @Ira: But the trivalent graphs may have multiple edges (but no loops). And even counting those wouldn't help to solve the problem I think. If I get it right, the problem asks for the number of 1-factors of the complement of $2nK_3$. $\endgroup$
    – Wolfgang
    Commented Jan 31, 2012 at 19:15
  • $\begingroup$ @spanferkel: is the complement of $2nK_3$ the same as the complete tri-partitite graph $K_{2n, 2n, 2n}$? $\endgroup$
    – mhum
    Commented Jan 31, 2012 at 19:39

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .