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.
Best Answer
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. $$