Solution - P3978 [TJOI2015]概率论

Posted on Edited on

P3978 [TJOI2015]概率论

参考 rqyrqy 的题解（第一篇）：

设 fnf_n 表示 nn 个节点的树的形态数， gng_n 表示 nn 个节点的所有树的叶子总数。

首先看 ff ：

显然 f0=1f_0=1 。

现在有 nn 个节点。当根节点的左子树有 ii 个节点的时候，右子树有 n−i−1n-i-1 个节点。

那么有

fn=∑i=0n−1fi×fn−i−1f_n = \sum_{i=0}^{n-1} f_i \times f_{n-i-1}

这是卡特兰数的递推式，故 ff 的通项公式为

fn=C2nnn+1f_n = \frac{C_{2n}^n}{n+1}

接下来看 gg ：

  1. 对于一棵总共有 nn 个节点、有 kk 个叶子节点的二叉树，可以任意去掉一个叶子结点得到一棵有 n−1n-1 个节点的二叉树。

  2. 而对于一棵有 n−1n-1 个节点的二叉树，每个节点最多可以有 22 个儿子，总共有 2(n−1)2(n-1) 个空位，自己本生用掉 n−2n-2 个空位，故有 nn 个可以插叶子结点的地方，也就对应着 nn 棵 nn 个节点的二叉树。

  3. 这样子就相当于构成了一张二分图。左边是 n−1n-1 个节点的二叉树，右边是 nn 个节点的二叉树。而根据 11 ，每条边就对应着一个叶子结点。又根据 22 ，边的总数为 fn−1×nf_{n-1}\times n 。

故我们得出

gn=n⋅fn−1g_n = n\cdot f_{n-1}

答案为

ans=gnfn=n⋅fn−1fn=n⋅C2n−2n−1nC2nnn+1=n⋅(2n−2)!⋅n!⋅n!⋅(n+1)(2n)!⋅(n−1)!⋅(n−1)!⋅n=n⋅(n+1)2(2n−1)ans = \frac{g_n}{f_n} = \frac{n\cdot f_{n-1}}{f_n} = \frac{n\cdot \frac{C_{2n-2}^{n-1}}{n}}{\frac{C_{2n}^n}{n+1}} = \frac{n\cdot (2n-2)!\cdot n!\cdot n!\cdot (n+1)}{(2n)!\cdot (n-1)!\cdot (n-1)!\cdot n} = \frac{n\cdot (n+1)}{2(2n-1)}