对oceans_of_stars的T3爆标做法的基础结论的证明

我们要证明的结论如下：

• \(x\) 在 \([1,x-1]\) 中选取父亲，以这种方法构造树，节点 \(x\) 在其子树大小为 \(i\) 时的方案数为 \(\binom{n-i-1}{x-2}\)。

对于组合数有一个众所周知的结论：

然后把上面的选式转化一下，得到：\(\binom{n-i-1}{n-i-x+1}\)。

还是组合数好看，于是写成 \(C_{n-i-1}^{n-x-i+1}\)。注意到不在 \(x\) 子树内的数为 \(n-i\)，而其中有一个点肯定不能做父亲，那就是最后一个点，所以下面的数意义是 \(x\) 子树外能做父亲的点。由于只考虑比 \(x\) 值大的点的分布（当然，这些点的父亲可以 \(\lt x\)，但是不考虑 \(\lt x\) 的点的父亲），所以 \(n-x+1\) 表示 \(\ge x\) 的点（\(x\) 的父亲肯定不是自己，所以也要算上）。然后减去在 \(x\) 子树内的 \(i\) 个点，解释了选式的上下两项的含义。又由于 \(x\) 在 \([1,x-1]\) 中选取父亲的限制，所以情况是成组合数形式分布的。建议配合一定的打表找规律来理解这一点。