Question

Let $\sigma(n,m)$ be the number of trees with $n$ vertices ${ v_1, \dots, v_n }$ such that the matching number (the size of a maximum matching) is $m$.

I have been trying to compute the value of $\sigma(n,m)$ but I have been unsuccessful. It looks hard. Is it known? Any idea or suggestion about how can $\sigma$ be computed? Or any good bounds?

Answer 1

If $n=2m$, the answer is $2^{m-2} m! \binom{2m}{m} m^{m-2}$. Let $T_m = \sigma(n,m)$. We go through several transformations. We write $[n]$ for the set $\{ 1,2,\ldots, n \}$ and $[a,b]$ for $\{ a, a+1, \ldots, b \}$.

$T_m$ number of fully matched trees on $[2m]$.

$2 T_m$ number of fully matched trees on $[2m]$ equipped with a bipartite coloring.

$\frac{2}{\binom{2m}{m}} T_m$ number of fully matched trees where $[1,m]$ is colored white and $[m+1, 2m]$ is colored black.

$\frac{2}{m! \binom{2m}{m}} T_m$ number of fully matched trees on $[2m]$ where $i$ is matched to $m+i$.

So we need to show that the last number is $2^{m-1} m^{m-2}$. Let $U$ be one of the objects counted by the last number, and let $V$ be the tree on $[m]$ obtained by contracting the matched edges and labeling the contraction of $(i, i+m)$ by $i$. We claim that every tree $V$ on $[m]$ has $2^{m-1}$ preimages under this map. Proof: To reconstruct $U$ from $V$, for every edge $(i,j)$ of $V$, we must choose whether to join $i$ to $j+m$ or $j$ to $i+m$. This is $m-1$ independent binary choices. $\square$

I don't have any good ideas about $n>2m$, but my basic ideas would be (1) see if you can use Hall's marriage theorem to give a simple description of when a matching is maximal (2) write some code to generate a table of values, and see whether it appears in Sloane's encyclopedia of integer sequences. Looking up a table in Sloane is a bit of a black art. You should try entering several different diagonals, entering individual rows forwards and backwards, looking up any other sequences that come up in restating the problem (for example, Sloane's doesn't list $T_m$ but it does have $\frac{2}{m! \binom{2m}{m}} T_m$). I'd also factor some of the large entries in my table; if all of the prime factors of $\sigma(n,m)$ are $\leq 4n$, it seems likely there is a product formula; if not, I'd bet against it. Hmmm, this might make a good blogpost....