Number of non-isomorphic 2-factors of $K_n$

Question

Let $f(n,k)$ be the number of non-isomorphic 2-factors of $K_n$ containing exactly k components.

Explain why the recurrence relation

$$ f(n,k) =f(n-3,k-1)+f(n-k,k)$$ holds for $n \geq 4 $ and $1 \leq k \leq floor(\frac{n}{3}) $ with $f(n,0) =0$ for all n $f(n,1) =1$ for all $n \geq 3$, and 0 otherwise $f(n,k)=0$ whenever $k > floor(\frac{n}{3})$

Attempt: I understand why the initializations make sense and I know that all 2-factors found in such way will be hamiltonian cycles but I cannot explain the recursion. I would appreciate any help

Answer 1

An isomorphism class of $k$-component $2$-factors of $k_n$ is uniquely represented by a partition $n = n_1 + n_2 + \dots + n_k$ in which $n_1 \ge n_2 \ge \dots \ge n_k \ge 3$.

There are two cases for such a partition:

• either $n_k = 3$, in which case there are $f(n-3,k-1)$ ways to choose $n_1, \dots, n_{k-1}$,
• or $n_k \ge 4$, in which case $(n_1-1)+(n_2-1)+\dots+(n_k-1)$ is a partition of $n-k$ satisfying the same constraint, and there are $f(n-k,k)$ such partitions.