How many disjoint subsets?
I have a question about combinatorics. I have the following set: $$M = \{ 1,2,...,n \}$$
How many disjoint subsets $$A\subseteq M, \quad |A| = 2$$ are there? For the future, how do I approach questions like these? Thanks in advance for your help
EDIT: $n$ is even. I want to know how many ways there are to split $M$ into disjoint subsets of size $2$. If this is any help, I am trying to figure out how many permutations in $S_n$ exist, that are involutions as well as derangements. For $n$ odd there are none, that's what I've shown so far. For $n$ even, I can write the permutation in brackets of size two (I don't know how you call this way of writing a permutation down). The order of the sets do not matter.
$\endgroup$ 62 Answers
$\begingroup$Let $A_n$ be the number of ways of partitioning an $n$-element set $M$ into $2$-element subsets. Pick $x \in M$. There are $n - 1$ choices for the element that is going to belong to the same partition as $x$, and then the remaining $n - 2$ elements can be partitioned into $2$-element subsets in $A_{n - 2}$ ways. Clearly $A_1 = 0$ and $A_2 = 1$, so we have:
\begin{align} A_n &= (n - 1)A_{n-2}\\ A_2 &= 1\\ A_1 &= 0 \end{align}
Hence $A_n = 0$ for odd $n$ and for even $n$ we have:
$$ A_{n} = 1 \cdot 3 \cdot \ldots \cdot n -1. $$
$\endgroup$ 5 $\begingroup$Since $n$ is even, say $n=2k$ for some integer $k$. How many ways are there to pick a pair of these integers? $$ \binom{2k}{2} $$ How many ways are there to pick a pair from the remaining numbers? $$ \binom{2k-2}{2} $$ So, the number of tuples (order matters for now) of the form $(A_1, \dots, A_k)$, where each $\lvert A_i \rvert = 2$ is given by the multinomial coefficient$$ \binom{2k}{\underbrace{2 \; 2 \; \cdots \; 2}_{k}} = \binom{2k}{2} \binom{2k-2}{2} \cdots \binom{2}{2} = \frac{(2k)!}{2! \; 2! \; \cdots \; 2!}. $$
To get the number of sets of the form $\{ A_1, \dots, A_k \}$, where each $\lvert A_i \rvert = 2$, you measure the redundancy. How many times did each size $k$ set get counted as a $k$-tuple? The number of permutations of size $k$ is $k!$, so the number of involutive derangements is $$ \frac{1}{k!} \binom{2k}{\underbrace{2 \; 2 \; \cdots \; 2}_{k}} = \frac{(2k)!}{k! \; (2!)^k}. $$ Miraculously, this expression simplifies further! Notice that the denominator is equivalent to the product of the first $k$ even numbers $2 \cdot 4 \cdots 2k$; hence your count is is just the product of the first $k$ odd numbers $$ (2k - 1)!! = 1 \cdot 3 \cdots (2k - 1). $$
Here are the first couple values in this sequence: \begin{array}{c|rrrrr} k & 1 & 2 & 3 & 4 & 5 \\ \hline (2k-1)!! & 1 & 3 & 15 & 105 & 945 \end{array}
$\endgroup$ 1
