Find a recurrence to the number of 1-factors in a complete 2n graph.
This is what I have.
For n=1, we have 1 1-factor for a complete graph of 2 nodes.
For n=2, we have 2 1-factors for a complete graph of 4 nodes.
For n=3, we have 5 1-factors for a complete graph of 6 nodes.
Then, supposedly, we have Catalan recurrence. But, the solution says the recurrence is $a_n = (2n-1)a_{n-1}$.
I don't get what is wrong here.
On 4 nodes, I personally count 3 1-factors : if vertices are $x_1,x_2,x_3,x_4$, then there are $\{x_1x_2,x_3x_4\}$, $\{x_1x_3,x_2x_4\}$ and $\{x_1x_4,x_2x_3\}$.
For the general recurrence : Let the vertices be $x_1,\dots,x_{2n}$. To choose the edge containing $x_1$ in the 1-factor (which is a matching) we have $2n-1$ choices. Let's say we have picked $x_i$. Then, we can build all 1-factors containing $x_1x_i$ by adding $x_1x_i$ to the 1-factors of the complete graph on $\{x_2,\dots,x_{i-1},x_{i+1},\dots,x_{2n}\}$ (all vertices except $x_1$ and $x_i$). We know that there are $a_{n-1}$ such 1-factors.
Thus, we have $2n-1$ choices for the edge containing $x_1$ and then $a_{n-1}$ choices for the matching for the rest of the graph. Thus, $a_n=(2n-1)a_{n-1}$.