How I solved Tree Expectancy (EXPTREE)

This post is about this question.

The first thing I noted was that the total trees with $N$ nodes are $C_{n-1}$ (Catalan Number). So if we consider the size of subtrees rooted at children then we get an ordered tuple $(a_1, a_2 … a_k)$ where $a_1+a_2 … a_k=n-1$. Thus it is evident that:

\[C_{n-1} = \sum_{a_1+a_2+...a_k=n-1}C_{a_1-1}C_{a_2-1}..C_{a_k-1}\tag{$n\ge 1$}\]

Now consider the expected value of number of vertices as $E_n$. Suppose we change only a particular parent, say, the first, then we will have $C_{a_1-1}E_{a_1}$ total such nodes in that children and considering permutations of other children we will have corresponding to this children $(C_{a_1-1}E_{a_1})C_{a_2-1}C_{a_3-1}…C_{a_k-1}$ total such vertices, hence total vertices from varying all children, $T_n$ will be:

\[T_n=\sum_{a_1+a_2+...a_k=n-1}C_{a_1-1}C_{a_2-2}...C_{a_k-1}\left(E_{a_1}+E_{a_2}...E_{a_n}\right)\tag{$n\ge 1$}\]

we need to also consider the case when $k=1$ where the root node will be such a vertex where we will only have $1$ child with $N-1$ nodes, i.e. $C_{(n-1)-1}$ such root nodes. Therefore (in particular $E_1=0$):

\[E_{n}=\frac{\#\text{total such nodes in all trees with n nodes}}{\#\text{total trees with n nodes}}=\frac{T_n+C_{n-2}}{C_{n-1}}\tag{$n\ge 2$}\]

Now $T_n$ can be simplified as follows ($n\ge 3, T_0=0, T_1=0$):

\[\begin{align}T_n&=\sum_{a_1}C_{a_1-1}\sum_{a_2+a_3+..a_k=n-a_1-1}C_{a_2-2}...C_{a_k-1}\left(E_{a_1}+E_{a_2}...E_{a_n}\right)\\ &=\sum_{a_1}C_{a_1-1}\left(E_{a_1}\sum_{a_2+a_3+...a_k=n-a_1-1}C_{a_2-1}C_{a_3-1}...C_{a_k-1}+\sum_{a_2+a_3+...a_k=n-a_1-1}C_{a_2-1}C_{a_3-1}...C_{a_k-1}(E_{a_2}E_{a_3}...E_{a_k})\right)\\ &=\sum_{\alpha=1}^{n-1}\underbrace{C_{\alpha-1}(E_{\alpha}}C_{n-\alpha-1}+T_{n-\alpha})\\ &=C_0(E_1C_{n-2}+T_{n-1})+\sum_{\alpha=2}^{n-1}C_{n-\alpha-1}(T_{\alpha}+C_{\alpha-2})+C_{\alpha-1}T_{n-\alpha}\\ &=T_{n-1}+\sum_{\alpha=2}^{n-1}C_{n-\alpha-1}T_{\alpha}+\underbrace{\sum_{\alpha=2}^{n-1}C_{\alpha-2}C_{n-\alpha-1}}_{C_{n-2}}+\sum_{\alpha=2}^{n-1}C_{\alpha-1}T_{n-\alpha}\\ &=T_{n-1}+C_{n-2}+2\sum_{\alpha=1}^{n-1}C_{\alpha-1}T_{n-\alpha}-(C_0T_{n-1}+C_{n-2}T_1)\\ T_n&=C_{n-2}+2\sum_{\alpha=1}^{n-1}C_{\alpha-1}T_{n-\alpha}=C_{n-2}+2\sum_{\alpha=1}^{n}C_{\alpha-1}T_{n-\alpha} \end{align}\]

So:

\[T_n=C_{n-2}+2(C_0T_{n-1}+C_1T_{n-2}+...C_{n-1}T_0)\tag{$n\ge3$}\]

We can verify these relations with (values in red are defined to satisfy the relations):

\[\begin{array}{c|ccc} n&C_n&E_n&T_n&T_n+C_{n-2}\\\hline 0&1&?&\color{red}{0}&?\\ 1&1&0&\color{red}{0}&0\\ 2&2&1&0&1\\ 3&5&1&1&2\\ 4&14&6/5&4&6\\ 5&42&10/7&15&20\\ 6&132&5/3&56&70 \end{array}\]

Let generating function of $T_n$ be $U(x)$ such that:

\[U(x)=T_0+T_1x+T_2x^2+...=T_3x^3+T_4x^4+...=x^3+4x^4+15x^5+...\]

and as we know for Catalan numbers:

\[A(x)=C_0+C_1x+C_2x^2+...=1+x+2x^2+5x^3+...=\frac{1-\sqrt{1-4x}}{2x}\]

Now we have:

\[\begin{align} U(x)A(x)&=\underbrace{T_0C_0+(T_1C_0+C_1T_0)x}_0+(T_2C_0+T_1C_1+T_0C_2)x^2+(T_3C_0+T_2C_1+T_1C_2+T_0C_3)x^3+...\\ &=\frac12(T_3-C_1)x^2+\frac12(T_4-C_2)x^3...\\ UA&=\frac12\frac Ux-\frac12(A-1)x\\ 2UAx&=U-(A-1)x^2\\ U&=\frac{(1-A)x^2}{2Ax-1}=\frac12\frac{1-2x-\sqrt{1-4x}}{\sqrt{1-4x}}x \end{align}\]

So:

\[U=\frac x2\frac{(1-2x)}{\sqrt{1-4x}}-\frac x2\]

Using Binomial Theorem:

\[\begin{align} U+\frac x2&=\frac x2(1-2x)(1-4x)^{-1/2}\\ &=\frac x2(1-2x)\left(\binom{-1/2}0+\binom{-1/2}1(-4x)+\binom{-1/2}2(-4x)^2+...\right) \end{align}\]

Coefficient of $x^{n+1}$ ($n\ge 2$) in that would be:

\[\begin{align} T_{n+1}&=\frac12\binom{-1/2}n(-4)^n-\binom{-1/2}{n-1}(-4)^{n-1}\\ &=\frac12\frac{\left(-\frac12\right)\left(-\frac32\right)\left(-\frac52\right)...\left(-\frac{2n-1}2\right)}{n!}(-4)^n-\frac{\left(-\frac12\right)\left(-\frac32\right)\left(-\frac52\right)...\left(-\frac{2n-3}2\right)}{(n-1)!}(-4)^{n-1}\\ &=\frac12\frac{(2n-1)!!}{n!}2^n-\frac{(2n-3)!!}{(n-1)!}2^{n-1}\\ &=\frac12\frac{(2n-1)!!(2n)!!}{n!(2n)!!}2^n-\frac{(2n-3)!!(2n-2)!!}{(n-1)!(2n-2)!!}2^{n-1}\\ &=\frac12\frac{(2n)!}{n!n!}-\frac{(2n-2)!}{(n-1)!(n-1)!}\\ &=\frac{(2n-2)!}{(n-1)!(n-1)!}\left(\frac{2n(2n-1)}{2n^2}-1\right)\\ &=\binom{2n-2}{n-1}\frac{n-1}n\\ T_{n+1}&=\binom{2n-2}{n} \end{align}\]

Hence:

\[\begin{align}E_n&=\frac{\binom{2n-4}{n-1}+\frac1{n-1}\binom{2n-4}{n-2}}{\frac1n\binom{2n-2}{n-1}}\\ &=\frac{n(n-1)}{2(2n-3)} \end{align}\]

Now define $P=n(n-1)$ and $Q=2(2n-3)$. We can easily find modular inverse using Fermat’s theorem and calculate accordingly:

C++ Code:

---