组合数学基础
组合数
定义 1 对于实数 \(a\) 和非负整数 \(b\)，\(a\) 的 \(b\) 次下降幂 \(a^{\underline b}\) 定义为
\(b\) 是负数时似乎也有定义，但我在网上看到了 \(>1\) 种不同的说法，这里就不讨论了。
定义 2 对于实数 \(a\) 和非负整数 \(b\)，\(a\) 的 \(b\) 次上升幂 \(a^{\overline b}\) 定义为
定义 3 对于实数 \(a\) 和非负整数 \(b\)，组合数 \(\binom ab\) 定义为
不在定义域内的组合数我们规定它们的值为 \(0\)。组合数 \(\binom{a}{b}\) 在 \(a\) 是非负整数时有组合意义：从 \(a\) 个物品中选 \(b\) 个的方案数。由组合意义我们可以得到一些式子，当然直接推也是容易的，它们有些在 \(a\) 是实数时也成立。
引理 1（组合数递推 1）对于所有实数 \(a\) 和非负整数 \(b\)，有
引理 2（组合数递推 2）对所有实数 \(a\) 和正整数 \(b\)，有
引理 3（上指标反转）对所有实数 \(a\) 和非负整数 \(b\)，有
引理 4（上指标求和 1）对所有非负整数 \(a,b\)，有
证明考虑枚举最后一个元素的位置。
定理 1（广义二项式定理）对于实数 \(a,b,\alpha\) 满足 \(|\frac{a}{b}|<1\)，有
证明考虑对 \((1+x)^{\alpha}\) 进行麦克劳林展开，代入 \(x=\frac{a}{b}\) 再乘以 \(b^{\alpha}\) 即可。级数在 \(|\frac{a}{b}|\ge 1\) 时发散。
P7481 梦现时刻
给定 \(n,m\)，对每组 \(1\le a,b\le m\) 求出 \(F(a,b)=\sum_{i=0}^{b}\binom{b}{i}\binom{n-i}{a}\)。
\(n\le 10^9,~m\le 5000\)
考虑使用递推求解。
考虑如何求 \(\binom{b-1}{i-1}\binom{n-i}{a+1}\)：
于是可以得到递推式。
第二类斯特林数
定义 4 对于非负整数 \(a,b\)，第二类斯特林数 \(\begin{Bmatrix}a\\b\end{Bmatrix}\) 定义为将 \(n\) 个有标号小球放到 \(m\) 个无标号箱子（箱子不能为空）的方案数。
引理 5
引理 6（拆幂）
P2791 幼儿园篮球题
模板题。
CF1097G Vladislav and a Great Legend
请点击标题链接查看题解。
分拆数
表示 \(n\) 个无标号小球的无序划分方案数。我只会 \(O(n^2)\) 做法。
贝尔数
定义为斯特林数的一行之和，组合意义表示 \(n\) 个有标号小球的无序划分方案数。其 EGF 显然为 \(e^{e^x-1}\)。
单位根反演
LGV 引理
在 DAG 上有一组起点 \(s_{1\sim n}\) 和一组终点 \(t_{1\sim n}\)，\(p\) 是 \(n\) 阶排列，引理指出，\(s_i\to t_{p_i}\) 的两两点不交的路径组数乘以 \((-1)^{\#(p)}\) 对全体 \(n\) 阶排列 \(p\) 求和等于
证明比较显然，对于一组不合法的路径，找到起点编号最小的和其他路径有交的路径，取和它交点距起点最近的一条路径，若有多条则取起点编号最小的，随后交换二者的终点，这显然构成一组不合法方案的匹配，且匹配边两侧贡献相反，于是相互抵消。
对于向右向下的网格 DAG，如果恰好只在 \(p\) 为单位置换的时候存在点不交路径组，那么上面的行列式就等于答案。
杨表
https://www.cnblogs.com/aquizahv/p/18858693#robinson-schensted-correspondence
https://www.cnblogs.com/yyyyxh/p/young_tableau.html
一些格子，每一行格子的数量都不少于下一行格子的数量，记第 \(i\) 行包含 \(\lambda(i)\) 个格子。一个格子的勾长 \(h(i,j)\) 定义为同一行在其右边的格子数+同一列在其下方的格子数+1。
向格子中填入数字，使得每行单调不降，每列单调上升，这样的东西称为半标准杨表。
钩子公式：将 \(1\sim n\) 的排列填入 \(n\) 个格子的半标准杨表方案数为
每个格子值域为 \(1\sim k\)，形状为 \(\lambda\) 的半标准杨表数量为：
Robinson-Schensted correspondence