TJOI 2015 概率论题解

题意

求 \(n\) 个点随机生成的有根二叉树（所有互不同构的二叉树出现情况等概率）的叶子节点数的期望值。

题解

70

答案显然是 \(\dfrac{g(n)}{f(n)}\) ，\(g(n)\) 是 \(n\) 个点为所有二叉树的叶子总数， \(f(n)\) 是 \(n\) 个点能生成的二叉树数。

一棵树可以用左右儿子与根节点拼接而成。

显然 \(f_i=\sum_{j=0}^{i-1} f_j f_{i-j-1}\)

同理 \(g\) 也可以用 \(f\) 转移，需要高精度。

当然考试后我懒得写用 py 验证了一下正确性。

n = int(input())
f = []
g = []
for i in range(0, 101):
    f.append(0)
    g.append(0)

f[0] = f[1] = g[1] = 1

for i in range(2, n + 1):
    for j in range(0, i):
        f[i] += f[j] * f[i - j - 1]
        g[i] += g[j] * f[i - j -  1] + f[j] * g[i - j - 1]

ans = 1.0 * g[n] / f[n]
print('%.9f' % ans)

100

前置知识：生成函数，卡特兰数，牛顿二项式定理。

1

我们要观察 \(f\) ：这其实就是卡特兰数的递推式。即 \(f(n)\) 是卡特兰数第 \(n\) 项。

先补一课：卡特兰数的封闭形式。

对于卡特兰数 \(f_i=\sum_{j=0}^{i-1} f_j f_{i-j-1}\) ，且 \(f_0=f_1=1\) ，设其生成函数 \(F(x)=\sum_{i\ge0}f_i x^i\)

\(f\) 的递推式很像卷积，可以将 \(F\) 卷起来：

\(F^2(x)=\sum_{i\ge 0} x^i\sum_{j=0}^{i}f_j f_{i-j}\)

发现 \(x\) 的次数与我们想要的形式差了 1 ，变化一下。

\(xF^2(x)=\sum_{i\ge 1} x^i\sum_{j=0}^{i-1}f_j f_{i-j-1}=\sum_{i\ge 1}f_i x^i\)

就相差 \(i=0\) 项，所以 \(xF^2(x)+1=F(x)\) ，解得 \(F(x)=\dfrac{1\pm\sqrt{1-4x}}{2x}\)

如何取舍？分子有理化： \(F(x)=\dfrac{2}{1\mp\sqrt{1-4x}}\) ，带入 \(x=0\) ，得到常数项。

发现符号时加号时满足 \(f_0=F(0)=1\) ；但减号时分母为 0 ，舍去

所以 \(F(x)=\dfrac{1-\sqrt{1-4x}}{2x}\)

2

同理，我们来处理叶子个数 \(g\) ，

\(g_i=[i=1]+\sum_{j=0}^{i-1}f_j g_{i-j-1}+g_j f_{i-j-1}\)

设 \(g\) 的生成函数为 \(G\) ，则 \(G(x)=2xF(x)G(x)+x^1\)

解得 \(G(x)=\dfrac{x}{1-2xF(x)}=\dfrac{x}{\sqrt{1-4x}}\)

根据牛顿二项式定理，

\[\begin{aligned} G(x)&=x(1-4x)^{-\frac{1}{2}}\\ &=x\sum_{i\ge 0}\binom{-\frac{1}{2}}{i}(-4x)^i\\ &=x\sum_{i\ge 0}(-4)^i x^i\dfrac{(-\frac{1}{2})^{\underline{i}}}{i!}\\ &=x\sum_{i\ge 0}x^i\prod_{j=1}^i \dfrac{-(2j-1)}{2\times j}\times(-4) \end{aligned} \]

连乘不连续，考虑化成连续。

\[=x\sum_{i\ge 0}x^i\prod_{j=1}^i\dfrac{(2j-1)(2j)}{(2j)(2j)}\times 4\tag{1} \]

这样上下都连续了。

\[G(x)=x\sum_{i\ge 0} x^i\dfrac{(2i)!}{(i!)^2} \]

得到封闭形式。求 \(g_n\) 就是 \(x^n\) 项的系数。

\(g_n=\dfrac{(2n-2)!}{(n-1)!^2}\)

带入卡特兰数通向公式 \(f_n=\binom{2n}{n}-\binom{2n}{n-1}=\)

所以化简可得 \(ans=\dfrac{g_n}{f_n}=\)