Proof for a recursive relation for counting matching in a graph

Question

Theorem: The sum of the number of $(1,2,3,\ldots n)$ matching[hosoya index] in a complete graph with $n$ vertices $K_n$ is given by the recursive formula:

$M_n = M_{n-1} + (n-1)M_{n-2}$

$M_1 = 1$ , $M_2 = 2$

---

Can anyone provide a proof for this recurrence relation?

Answer 1

We will use the substitution method this for the following recurrence:

$T(n) = T(n - 1) + (n - 1)T(n - 2)$.

$= (T(n - 2) + (n - 2)T(n - 3)) + (n - 1)(T(n - 3) + (n - 3)T(n - 4))$

$= T(n - 2) + (n - 2)T(n - 3) + (n - 1)T(n - 3) + (n - 1)(n - 3)T(n - 4)$

$= (T(n - 3) + (n - 3)T(n - 4)) + (n - 2)(T(n - 4) + (n - 4)T(n - 5)) + (n - 1)(T(n - 4) + (n - 4)T(n - 5)) + (n - 1)(n - 3)(T(n - 5) + (n - 5)T(n - 6))$

From this, we can use the variable $i$ to represent the amount of iterations.

$= T(n - i) + (n - 1)T(n - i - 1) + (n - i + 1)(T(n - i - 1) + (n - i - 1)T(n - 2i + 1)) + (n - i)(T(n - i - 1) + (n - i - 1)T(n - 2i + 1)) + (n - 1)(n - i)(T(n - 2i + 1) + (n - 2i + 1)T(n - 2i))$

$= T(n - i) + (n - 1)T(n - i - 1) + ((n - i + 1) + (n - i))(T(n - i - 1) + (n - i - 1)T(n - 2i + 1)) + (n - 1)(n - i)(T(n - 2i + 1) + (n - 2i + 1)T(n - 2i))$

Now, we can calculate the base of the function $T(n)$. We decide to use the base value 1 instead of 2 because some of the function calls return a lower value than others. For instance, the value $n - 2i$ is lower than $n - i$.

Therefore, we can express the base value by $n$ from the equation below isolating $i$.

$n - 2i = 1 \rightarrow i = \frac{n - 1}{2}$

Also, recall $n - \frac{n - 1}{2} = \frac{n + 1}{2}$.

$= T(\frac{n + 1}{2}) + \frac{n + 1}{2}T(\frac{n + 1}{2} - 1) + (\frac{n + 1}{2} + 1)(T(\frac{n + 1}{2} - 1) + (\frac{n + 1}{2} - 1) * 2) + (n - 1)(T(\frac{n + 1}{2} - 1) + (\frac{n + 1}{2} - 1) * 2) + (n - 1)(\frac{n + 1}{2})(2 + 2 * 1)$

$= T(\frac{n + 1}{2}) + (\frac{n + 1}{2})T(\frac{n + 1}{2} - 1) + \frac{n + 3}{2}(T(\frac{n + 1}{2} - 1) + n - 1) + (n - 1)(T(\frac{n + 1}{2} - 1) + n - 1) + \frac{4n^2 - 4}{2}$

$= T(\frac{n + 1}{2}) + \frac{n + 1}{2}T(\frac{n + 1}{2} - 1) + \frac{n + 3}{2}T(\frac{n + 1}{2} - 1) + n^2 + 3n - \frac{n + 3}{2} + (n - 1)T(\frac{n + 1}{2} - 1) + n^2 - 2n + 1 + 2n - 2$

$ = T(\frac{n + 1}{2}) + (n + 2)T(\frac{n + 1}{2} - 1) + 4n^2 + n - \frac{n + 3}{2} + (n - 1)T(\frac{n + 1}{2} - 1) - 1$

$= T(\frac{n + 1}{2}) + 2nT(\frac{n + 1}{2} - 1) + 4n^2 + n - \frac{n + 3}{2} - 1$

$= T(\frac{n + 1}{2}) + 2nT(\frac{n + 1}{2} - 1) + 4n^2 + \frac{n + 3}{2} - 1$

$= T(\frac{n + 1}{2}) + 2nT(\frac{n + 1}{2} - 1) + 4n^2 + \frac{n + 1}{2}$

When we using the substitution method, we found that $T(\frac{n + 1}{2})$ corresponds to $M_4$ and $T(\frac{n + 1}{2} - 1)$ corresponds to $M_3$.

$= M_4 + 2nM_3 + 4n^2 + \frac{n + 1}{2}$

We know that $M_3 = 4$ and $M_4 = 10$.

$= 10 + 12n + 4n^2 + \frac{n + 1}{2}$

$= 4n^2 + \frac{24n + n + 1}{2} + 10$

$= 4n^2 + \frac{25n + 1}{2} + 10$

$= 4n^2 + 12.5n + 10.5$

From this equation, we can eventually describe its bounds by $\Theta(n^2)$ and prove it by induction.

Answer 2

Consider vertex number $n$. There are two cases. Either vertex $n$ is not matched with anything, in which case there are $M_{n-1}$ matchings on the remaining $n-1$ vertices, or vertex $n$ is matched with something. In the latter case, there are $n-1$ choices for the vertex that vertex $n$ is paired with, then $M_{n-2}$ ways to match the other $n-2$ vertices.