题意：求一棵\(n\)个节点的有根二叉树的叶子节点的期望个数。设\(f_n\)表示\(n\)个点的二叉树个数，\(g_n\)表示\(n\)个点的所有二叉树的叶子节点数之和。显然\(f_n\)为\(\text{Catalan}\)数，考虑如何求\(g_n\)。一个结论是：\(g_n=f_{n-1}\timesn\)。证明：对于每一

题面传送门description求\(n\)个结点的无标号有根二叉树叶子结点的期望个数。\(1\leqn\leq10^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我们就要有足够的敏感度知道这是卡特兰数然后考虑叶子个数我们假设我们