2
$\begingroup$

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$
  • 2
    $\begingroup$ Your question is not clear to me. You you want to know how many subsets has a partition of $M$ if these subsets have two elements? If this is your question the answer is simple: $n/2$ (or its integer par if $n$ is odd). $\endgroup$ – ajotatxe Apr 15 '15 at 17:55
  • 2
    $\begingroup$ Do you mean how many two element subsets are there of $M$, or how many ways to split $M$ into disjoint two element subsets? If so, what happens if $n$ is odd? $\endgroup$ – Ross Millikan Apr 15 '15 at 17:56
  • $\begingroup$ Sorry that I was not clear. 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 derangemengts. 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). $\endgroup$ – Doc Apr 15 '15 at 18:16
  • 1
    $\begingroup$ @MaxDoc You should edit your question to include the information you placed in your last comment, where it may be missed. In particular, it is important that readers are aware that $n$ is supposed to be even. $\endgroup$ – N. F. Taussig Apr 15 '15 at 18:30
  • 2
    $\begingroup$ Do you care about the order of the subsets in the partition? (I think I know the answer from the context that you included, but you should be clear in the question.) For $n=6$, is $\{ \{1,2\}, \{3,4\}, \{5,6\} \}$ counted as the same partition as $\{ \{1,2\}, \{5,6\}, \{3,4\} \}$? In other words, are you interested in a set of sets of size $2$ or a tuple of sets of size $2$? $\endgroup$ – Sammy Black Apr 15 '15 at 18:45
5
$\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$
  • $\begingroup$ Very nice solution. $\endgroup$ – Sammy Black Apr 15 '15 at 20:07
  • $\begingroup$ Great. Thanks a lot. $\endgroup$ – Doc Apr 16 '15 at 16:06
  • $\begingroup$ shouldn't it be ".. there are $n$ choices to pick $x$, $n-1$ choices to pick $y$, divided by $2$ because a subset is ordered, thus $A_{n} = {n \choose 2} A_{n-2}$" ? $\endgroup$ – G Cab Jan 24 '17 at 14:47
  • $\begingroup$ @GCab: no. Try it with $n = 4$, say. $\endgroup$ – Rob Arthan Jan 24 '17 at 20:26
  • $\begingroup$ @RobArthan: thanks, ok, I saw now that the subsets are supposed to be unordered. So my supposition is going to be divided by $n/2$, leaving infact $(n-1)$ as a factor. $\endgroup$ – G Cab Jan 24 '17 at 21:51
2
$\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$
  • $\begingroup$ Thanks for your effort, the answer was very informative. $\endgroup$ – Doc Apr 16 '15 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.