Maximum number of ways to select $2$ element disjoint subsets from an $n$ set

Question

Suppose that we have the set $\{ 1, 2, \cdots, n\}$. I seek the number of ways to select $2$ element subsets, $s_1, s_2, \cdots, s_k$, such that the intersection of any $2$ of these subsets is the empty set. So far, my thinking has consisted of the fact that there are $\binom{n}{2}$ possible subsets. However, i'm struggling to proceed from here. Thank you in advance. For context, this problem is part of a larger graph theory problem that I am trying to solve.

Answer 1

Let $k$ denote the largest integer such that $k \leq \dfrac{n}{2}.$

That is, let $\displaystyle k = \left\lfloor \frac{n}{2} \right\rfloor.$

Then, you are looking for the number or distinct ways of forming a collection of $k$ disjoint subsets, where each subset has $(2)$ elements.

For illustrative purposes, first, consider the enumeration when $n = 7.$ You will be forming disjoint subsets, from the set $\{1,2,3,4,5,6,7\}$. Each such subset will have $(2)$ elements.

There are $~\displaystyle \binom{7}{2}~$ ways of choosing the first subset.

Then, there are $~\displaystyle \binom{5}{2}~$ ways of choosing the second subset, from the $(5)$ remaining elements.

Then, there are $~\displaystyle \binom{3}{2}~$ ways of choosing the third subset from the $(3)$ remaining elements.

---

Therefore, when $(n = 7)$, superficially, you would suppose that the number of satisfying collections of three subsets is

$$\binom{7}{2} \times \binom{5}{2} \times \binom{3}{2}. \tag1$$

For $(n = 7)$, the expression in (1) above is $\color{red}{\text{wrong}}.$

To understand why it is wrong, consider the collection of the following three subsets:

$$\{1,2\} ~~~\text{and}~~~ \{3,4\} ~~~\text{and}~~~ \{5,6\}. \tag2 $$

In the enumeration represented in (1) above, the subsets represented in (2) above will be counted $(3!)$ times, instead of only counting this group of subsets once. That is, there are $(3!)$ ways of ordering the three subsets represented in (2) above. The enumeration represented in (1) above represents counting each such ordering separately.

So, in the specific case of $n = 7$, you have to apply the overcounting adjustment factor of $~\displaystyle \frac{1}{k!}~$, where
$\displaystyle k = 3 = \left\lfloor \frac{7}{2} \right\rfloor.$

---

At this point, it is easy to come up with the general formula, that will apply to any $(n)$, using the considerations of $(n=7)$ as a guide.

As indicated at the start of this answer, let

$$k = \left\lfloor \frac{n}{2} \right\rfloor.$$

First,the expression in (1) above generalizes to

$$\binom{n}{2} \times \binom {n-2}{2} \times \cdots \times \binom{2 + n - 2k}{2} = \frac{n!}{[(n - 2k)!] \times 2^k}. \tag3 $$

Then, the expression in (3) above, coupled with the overcounting adjustment factor of $\dfrac{1}{k!}$ results in the accurate enumeration. Therefore, the final enumeration is

$$\frac{n!}{[(n - 2k)!] \times 2^k \times (k!)}.$$

Answer 2

Equivalently, you want to find the number of matchings in the complete graph $K_n$. See https://oeis.org/A000085.

If $k$ is fixed, instead see https://oeis.org/A100861.