P3978 [TJOI2015] 概率论 题解

题意：求一棵 \(n\) 个节点的有根二叉树的叶子节点的期望个数。

设 \(f_n\) 表示 \(n\) 个点的二叉树个数，\(g_n\) 表示 \(n\) 个点的所有二叉树的叶子节点数之和。

显然 \(f_n\) 为 \(\text{Catalan}\) 数，考虑如何求 \(g_n\)。一个结论是：\(g_n=f_{n-1} \times n\)。

证明：对于每一棵 \(n\) 个节点的二叉树（\(k\) 个叶子节点），我们都可以通过删去其中的一个叶子节点得到 \(k\) 棵 \(n-1\) 个点的二叉树，我们只需要计算一共会得到多少棵二叉树即可。正难则反，我们考虑每一棵 \(n-1\) 个点的二叉树会被得到几次。会发现我们可以在一棵 \(n-1\) 个点的二叉树上的 \(n\) 个位置上添加一个叶子节点，变为一棵 \(n\) 个节点的二叉树。为什么是 \(n\) 个位置？因为一共有 \(2 \times (n-1)\) 个位置，但是有 \(n-2\) 个位置已经有节点了，所以有 \(2\times (n-1)-(n-2)=n\) 个位置。所以每一棵 \(n-1\) 个节点的二叉树会被 \(n\) 棵 \(n\) 个点的二叉树得到，从而推出该式。

最终的答案期望为：\(\frac{g_n}{f_n}=\frac{f_{n-1}\times n}{f_n}=\frac{n (n+1)}{4n-2}\)。