description
求 \(n\) 个结点的无标号有根二叉树叶子结点的期望个数。
\(1\leq n\leq 10^9\)
solution
设 \(g_n\) 为 \(n\) 个点的有根无标号二叉树的个数，\(f_n\) 为所有 \(n\) 个点的有根无标号二叉树的叶子结点个数和，因为每种形态的二叉树是等概率出现的，所以答案为 \(\dfrac{f_n}{g_n}\)。
有转移：
-
\(g_0=1,f_0=0,f_{1}=1\)
-
\(g_n=\sum\limits_{i=0}^{n-1} g_{i}g_{n-i-1},f_{n}=2\sum\limits_{i=0}^{n-1}f_{i}g_{n-i-1}\)
设 \(G(x)\) 是 \(\{g_i\}_{i=0}^{\infty}\) 的生成函数，\(F(x)\) 是 \(\{f_i\}_{i=0}^{\infty}\) 的生成函数。
根据转移，有 \(G(x)=1+G^2(x)x\)，解得 \(G(x)=\dfrac{1\pm \sqrt{1-4x}}{2x}\)，因为 \(G(0)=g_0=1\)，所以 \(G(x)=\dfrac{1- \sqrt{1-4x}}{2x}\)。
还有 \(F(x)=2F(x)G(x)x+x\)，得 \(F(x)=\dfrac{x}{1-2xG(x)}=\dfrac{x}{\sqrt{1-4x}}\)。
因为 \(\sqrt{1-4x}=(1-4x)^{\frac{1}{2}}=\sum\limits_{i=0}^{\infty} \dbinom{\dfrac{1}{2}}{i} (-4x)^i\)
所以可以得到 \(f_n,g_n\) 的通项公式。
-
\(g_n=(-1)^n\dfrac{1}{2}\dbinom{\dfrac{1}{2}}{n+1}4^{n+1}\)
-
\(f_n=(-4)^{n-1} \dbinom{-\dfrac{1}{2}}{n-1}\)
所以
\(\begin{aligned} \dfrac{f_n}{g_n} &= \dfrac{(-4)^{n-1}\times(-\dfrac{1}{2})\times(-\dfrac{1}{2}-1)\times \dots\times (-\dfrac{1}{2}-n+2)\times \dfrac{1}{(n-1)!}}{(-1)^n\times \dfrac{1}{2}\times \dfrac{1}{2}\times (\dfrac{1}{2}-1)\times \dots \times (\dfrac{1}{2}-n)\times 4^{n+1}\times \dfrac{1}{(n+1)!}}\\ &=\dfrac{(-4)^{n-1}\times(-\dfrac{1}{2})\times(-\dfrac{1}{2}-1)\times \dots\times (-\dfrac{1}{2}-n+2)\times \dfrac{1}{(n-1)!}}{(-1)^n\times \dfrac{1}{4}\times (-\dfrac{1}{2})\times (-\dfrac{1}{2}-1)\dots \times (-\dfrac{1}{2}-n+1)\times 4^{n+1}\times \dfrac{1}{(n+1)!}}\\ &= -\dfrac{(n+1)!}{4\times (n-1)!\times (-\dfrac{1}{2}-n+1)} \\ &=\dfrac{n(n+1)}{4n-2} \end{aligned}\)
综上，答案为 \(\dfrac{n(n+1)}{4n-2}\)。