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}=\)
标签：4x,题解,TJOI,卡特兰,ge,dfrac,2015,sum,2j From： https://www.cnblogs.com/KonjakLAF/p/17323211.html