「BZOJ 4001」概率论-生成函数

求随机生成的一棵有根二叉树的叶子节点数的期望。

链接

BZOJ 4001

题解

首先 $n$ 个节点的二叉树个数是卡特兰数，我们用 $C(n)$ 表示，令 $f(n)$ 表示有 $n$ 个节点的二叉树的叶子节点个数，那么答案为 $\frac {f(n)} {C(n)}$。

我们很容易得到 $f(0) = 0, f(1) = 1$，枚举子树的大小，$n$ 个节点的二叉树，左子树有 $i$ 个节点，右子树共有 $C(n - i - 1)$ 种方案，而左右子树是对称的，我们有

$$f(n) = 2 \sum_{i = 0} ^ {n - 1}f(i)C(n - i - 1)$$

令 $G(x)$ 为 $C(n)$ 的生成函数，$F(x)$ 为 $f(n)$ 的生成函数，注意到上式是卷积的形式，卷积刚好对应生成函数的乘法，我们有

$$F(x) = 2x F(x)G(x) + x$$

而卡特兰数的生成函数为
$$G(x) = \frac {1 - \sqrt{1 - 4x}} {2x}$$
我们可以求得
$$F(x) = \frac {x} {\sqrt{1 - 4x}}$$

此时我们只需要求出 $F(x)$ 中 $x ^ n$ 的系数就可以了。

由广义二项式定理，有

$$\begin{aligned}F(x) &= \frac {x} {\sqrt{1 - 4x}} \\ &= x(1 - 4x) ^ {- \frac {1} {2}} \\ &= x \sum_{i = 0} ^ {\infty}\binom {- \frac 1 2} {i} (-4x) ^ i \\ &= x \sum_{i = 0} ^ {\infty} \frac {(-\frac 1 2) \times (-\frac 3 2) \times \cdots \times (- \frac 1 2 - i + 1)} {i !} (-4x) ^ i \\ &= x \sum_{i = 0} ^ {\infty} \frac {1 \times 3 \times \cdots \times (2i - 1)} {i !} 2 ^ ix ^ i \\ &= x \sum_{i = 0} ^ {\infty} \frac {(2i) !} {i ! \cdot i !} x ^ i \\ &= x\sum_{i = 0} ^ {\infty}\binom{2i} {i}x ^ i \end{aligned}$$

所以系数为 $\binom{2n - 2} {n - 1}$，而卡特兰数为 $\frac {(2n)!} {n!(n + 1)!}$。

故答案为

$$\frac {\binom{2n - 2} {n - 1}} {\frac {(2n)!} {n!(n + 1)!}} = \frac {n ^ 2 + n} {4n - 2}$$

代码

推导 5 小时，代码 1 分钟

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

/** * Copyright (c) 2017, xehoth * All rights reserved. * 「BZOJ 4001」概率论 25-10-2017 * 生成函数 * @author xehoth */ #include <bits/stdc++.h> int main() { double n; std::cin >> n; std::cout << std::fixed << std::setprecision(9) << (n * n + n) / (4 * n - 2); }