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$.



Number of independent sets of a random tree
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.$$


