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?
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....
This can be done using the canonical coloring of vertices of trees into 3 colors that can be found in
Let me briefly define this coloring (using my own choice of colors). A vertex is
Then it turns out that this has something to do with maximum matchings too. In particular, the number of vertices not covered by a maximum matching is # red vertices - # green vertices.
Using a description of this coloring by local rules, one can write functional equations for the generating series of trees according to the color of their vertices.
The results already mentioned show, at least implicitly, that $\sigma(n,m)$ can be computed efficiently.
But there is a simple characterisation that, as far as I know, might have been overlooked until now (please inform me if I'm the one who overlooked something!):
Roll an $n$-sided die repeatedly, and let $k$ be the largest number such that the first $n-k$ throws produce at least $k$ different numbers. Then $k$ has the same random distribution as the matching number of a uniformly chosen tree on $n$ labelled vertices.
This gives an expression for $\sigma(n,m)$ in terms of Stirling numbers of the second kind:
$$ \sigma(n,m) = \frac{n^{m-2}\cdot n!}{(n-m)!} \cdot \left(\genfrac\{\}{0pt}{}{n-m}{m} + (n-m)\cdot\genfrac\{\}{0pt}{}{n-m-1}{m}\right) $$
In my new paper Slither code and the independence number of a random tree I give a proof based on tweaking the Prüfer correspondence to something I call "slither code". Notice that the independence number of a tree is the number of vertices minus the matching number.
