Number of independent sets of a random tree

Question

Let $T_n$ be a random tree on $n$ labelled vertices chosen equiprobably among all $n^{n - 2}$ trees, and $I(T)$ be the number of distinct independent sets of a tree $T$. I'm interested in the average number $\mathrm{E}I(T_n)$ of independent sets of a random tree, at least asymyptotically.

Here are the values for a few small values of $n$ (obtained by generating all trees and counting their independent sets with dynamic programming):

$\mathrm{E}I(T_1) = 2$

$\mathrm{E}I(T_2) = 3$

$\mathrm{E}I(T_3) = 5$

$\mathrm{E}I(T_4) = \frac{33}{4} = 8.25$

$\mathrm{E}I(T_5) = \frac{341}{25} = 13.64$

$\mathrm{E}I(T_6) = \frac{4873}{216} \sim 22.56...$

$\mathrm{E}I(T_7) = \frac{89615}{2401} \sim 37.324...$

$\mathrm{E}I(T_8) = \frac{2023745}{32768} \sim 61.7598...$

$\mathrm{E}I(T_9) = \frac{54315721}{531441} \sim 102.2046...$

$\mathrm{E}I(T_{10}) = \frac{1691484561}{10000000} \sim 169.148...$

Here are a few questions I have:

1. The values of $\mathrm{E}I(T_n)$ seem to grow only so slightly faster than Fibonacci numbers. Naturally, we expect $\mathrm{E}I(T_n) \sim (\beta + o(1))^n$. What is the value of $\beta$? Is $\beta = \varphi = \frac{1 + \sqrt{5}}{2}$? UPD: numerically, $\beta$ seems to be around $1.657$.

2. I cannot help but notice that the denominator of $\mathrm{E}I(T_n)$ is $n^{n - 3}$ for $n \geq 3$, that is, in the expression $S_n / n^{n - 2}$ (where $S_n$ is the total number of independent sets over all trees with $n$ vertices) exactly a factor of $n$ is cancelled out upon reduction to smallest terms. Moreover, after the cancellation we persistently observe $S_n / n \equiv 1 \pmod n$ for $n > 3$. Is all of this a coincidence that eventually goes away, or is there something special about values of $S_n$ that explains it? UPD: both patterns seem to persist for $n$ up to $100$.

Answer 1

The exact average number of independent sets in a random labelled tree of $n$ vertices is $$ E_n = \sum_{k=0}^{n-1} \binom{n}{k} n^{1-k} (n-k)^{k-1}. $$

To prove this, use the Matrix Tree Theorem (or alternatively Ilya's method) to show that the number of labelled trees with a specified independent set of size $k$ is $n^{n-k-1} (n-k)^{k-1}$. This is certain to be a known formula.

It is unlikely that the sum has a closed form. To establish the asymptotics, one approach is to find the shape of the terms around the largest term. Apparently the largest term occurs when $k\approx cn$ where $c\approx 0.3075417$ is the solution to $$(1-c)^2 e^{-c/(1-c)}=c.$$ From this it follows that $$\lim_{n\to\infty} E_n^{1/n} = \frac{1}{(1-c)^{1-2c}\, c^c} \approx 1.655487913.$$