「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);
}

分享到