2
$\begingroup$

Possible Duplicate:
Number of equivalence relations splitting set into sets with exactly 3 elements

Given a set $S$ ($|S|$ even), I'm looking for the number of partitions of $S$, so that all elements of such partition have a cardinality of $2$.

  • 1
    I voted to close this as a duplicate (see above) because the o$n$ly difference to that question is the cardinality of the subsets, which is easily generalizable in the answers given there.2011-08-26

2 Answers 2

4

See Multinomial theorem: "The multinomial coefficients have a direct combinatorial interpretation, as the number of ways of depositing $n$ distinct objects into $m$ distinct bins, with $k_1$ objects in the first bin, $k_2$ objects in the second bin, and so on." Here however your bins are not distinct, so you have to divide by the number of bins factorial (you count every solution several times), in this case $(|S|/2)!$. So the answer to your question is:

$\frac{\ \displaystyle\binom{|S|}{2,2,\ldots,2}\ }{(|S|/2)!}$

4

The desired value is also known as the double factorial of $|S|-1$; that is, $(|S|-1)!!$. This is the product of all positive, odd integers less than $|S|$, $ (|S|-1)!! =(|S|-1)\cdot(|S|-3)\cdot(|S|-5) \cdots 5\cdot 3\cdot1.$