1
$\begingroup$

The main question I'm trying to solve is how many 1-factors are in $K_{2n}$ where $K_n$ is the complete graph on $n$ vertices.

Would it be correct to think of it as how many ways can you partition 2n elements into n subsets of size 2? Because that doesn't really make sense to me (it was an idea given to me by someone else).

For example,

when $n=2$ then the set of 2n = 4 elements, {$x_1,x_2,x_3,x_4$}, will have 6 subsets of size 2. But how would I determine how to partition the set into 2 subsets of size 2?

Overall, is this the right thought process? If not, how should I start solving this problem?

$\endgroup$
0
$\begingroup$

The idea you mention is indeed correct. A 1-factor is a 1-regular spanning sub-graph. A 1-regular spanning sub-graph is just a perfect matching - i.e. a set of edges with no vertices in common, such that every vertex is in one of these edges. The set of perfect matchings is in bijection with the set of ways to partition the vertex set into subsets of size 2.

Now, lets think about how to count these. Suppose we choose our first subset of size two - there are $\binom{2n}{2}$ ways of doing this. Now, we have $2n-2$ elements left to partition. There are $\binom{2n-2}{2}$ ways of choosing the next subset of size 2 and so on. However, we do not distinguish which order these sets are in, so we should divide by $n!$. In total, there should $\frac{1}{n!}\prod_{j=1}^n\binom{2j}{2}$ ways to partition this set. Now, $\binom{2j}{2}=\dfrac{2j(2j-1)}{2}=j(2j-1)$. We can write $$\frac{1}{n!}\prod_{j=1}^n\binom{2j}{j}=\frac{1}{n!}\prod_{j=1}^nj(2j-1)=\frac{1}{n!}\prod_{j=1}^nj\prod_{j=1}^n(2j-1).$$ Now, the middle term is clearly $n!$. For the third term, we can recognize that with a little manipulation, this is $\frac{(2n)!}{2^nn!}$ since $2^nn!$ will be the product of all the even terms in $(2n)!$, leaving only the odd terms. Thus, since the first and second terms cancel, the total number of ways to 1-factors is $\frac{(2n)!}{2^nn!}$.

$\endgroup$

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.