3978

题面传送门 description 求 \(n\) 个结点的无标号有根二叉树叶子结点的期望个数。 \(1\leq n\leq 10^9\) solution 设 \(g_n\) 为 \(n\) 个点的有根无标号二叉树的个数，\(f_n\) 为所有 \(n\) 个点的有根无标号二叉树的叶子结点个数和， ......

首先考虑当节点数为n时，有多少个二叉树 设\(f[i]\)表示节点为i时二叉树的个数，有 \[f[n]=\sum_{i=1}^{n-1}f[i]f[n-1-i] \]注意这种递推式子也是卡特兰数的一种形式，所以为卡特兰数 其实手写出前四项为1,2,5,14我们就要有足够的敏感度知道这是卡特兰数 然后 ......

定义 $f_i$ 为 $i$ 个节点组成的二叉树数量，$g_i$ 为 $i$ 个节点组成的二叉树的叶子节点个数之和 设当前 $i$ 个节点组成的二叉树有 $a$ 个叶子，容易发现分别删掉其中的 $1$ 个叶子节点就能得到一个对应的 $i - 1$ 个节点的二叉树，总共会有 $a$ 颗，可以发现每一个 ......