TJOI 2015 概率论 题解

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] = 1for 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}=\\)