Combinatorics

\(\large\rm Proof:\)

将上式带入下式得 \(:\)

整理得 \(:\)

根据组合恒等式 \(\dbinom{i}{j}\dbinom{j}{k}=\dbinom{i}{k}\dbinom{i-k}{j-k}\) 得 \(:\)

交换枚举顺序得 \(:\)

序列 \(a\) 的普通生成函数 \(\rm(Ordinary\ Generating\ Function,OGF)\) 被定义为形式幂级数 ：

\(a\) 既可以是有穷序列也可以是无穷序列，\(x\) 不具有实际意义，仅作为一个形式上的变量参与运算。

加减不必多说 ：

则有：

小球入盒问题是所有组合问题的基础，它计算的是形如 “\(n\) 个球放进 \(m\) 个盒子的方案数” 的一类问题，在这类问题中一般存在三种限制 ：

• 小球是否有编号。
• 盒子是否有编号。
• 盒子中球的数量是无限制，至少一个还是至多一个。

理由同上，方案数为 ：

\(\rm Prufer\) 序列可以将一颗结点数为 \(n\) 的有标号无根树用一个长度为 \(n-2\)，值域为 \([1,n]\) 的数列唯一表示，即有标号无根树和 \(\rm Prufer\) 序列呈双射关系。

具体来说，有标号无根树的构建方式如下：

• 将要计数的总体分成很多个部分，每个部分分别计算贡献。
• 有些时候一个集合 \(S\) 联合产生贡献，为了避免算重，可以将这个集合的贡献放在其中的某个元素上计算，比如标号最小的那一个。
• 可以考虑划分阶段，每次加入一个元素时计算答案增量。
• 如果需要计算在一个大的部分中选…