组合数学基础

组合数

定义 1 对于实数 \(a\) 和非负整数 \(b\)，\(a\) 的 \(b\) 次下降幂 \(a^{\underline b}\) 定义为

\[ a^{\underline b}=\prod_{i=0}^{b-1}(a-i) \]

\(b\) 是负数时似乎也有定义，但我在网上看到了 \(>1\) 种不同的说法，这里就不讨论了。

定义 2 对于实数 \(a\) 和非负整数 \(b\)，\(a\) 的 \(b\) 次上升幂 \(a^{\overline b}\) 定义为

\[ a^{\overline b}=\prod_{i=0}^{b-1}(a+i) \]

定义 3 对于实数 \(a\) 和非负整数 \(b\)，组合数 \(\binom ab\) 定义为

\[ \binom ab=\frac{a^{\underline b}}{b!} \]

不在定义域内的组合数我们规定它们的值为 \(0\)。组合数 \(\binom{a}{b}\) 在 \(a\) 是非负整数时有组合意义：从 \(a\) 个物品中选 \(b\) 个的方案数。由组合意义我们可以得到一些式子，当然直接推也是容易的，它们有些在 \(a\) 是实数时也成立。

引理 1（组合数递推 1）对于所有实数 \(a\) 和非负整数 \(b\)，有

\[ \binom{a}{b}=\binom{a-1}{b}+\binom{a-1}{b-1} \]

引理 2（组合数递推 2）对所有实数 \(a\) 和正整数 \(b\)，有

\[ \binom{a}{b}=\frac{a}{b}\binom{a-1}{b-1} \]

引理 3（上指标反转）对所有实数 \(a\) 和非负整数 \(b\)，有

\[ \binom{a}{b}=(-1)^{b}\binom{b-a-1}{b} \]

引理 4（上指标求和 1）对所有非负整数 \(a,b\)，有

\[ \sum_{i=0}^{a}\binom{i}{b}=\binom{a+1}{b+1} \]

证明考虑枚举最后一个元素的位置。

定理 1（广义二项式定理）对于实数 \(a,b,\alpha\) 满足 \(|\frac{a}{b}|<1\)，有

\[ (a+b)^{\alpha}=\sum_{i=0}^{+\infty}\binom{\alpha}{i}a^ib^{\alpha-i} \]

证明考虑对 \((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}{i}\binom{n-i}{a}=\binom{b-1}{i-1}\Bigg(\binom{n-i+1}{a+1}-\binom{n-i}{a+1}\Bigg)+\binom{b-1}{i}\binom{n-i}{a} \]

考虑如何求 \(\binom{b-1}{i-1}\binom{n-i}{a+1}\)。我们不能让上指标同时加 \(1\)，但是可以让下指标同时加 \(1\)，如下：

\[ \binom{b-1}{i-1}\binom{n-i}{a+1}=\Bigg(\binom{b}{i}-\binom{b-1}{i}\Bigg)\binom{n-i}{a+1} \]

于是可以得到递推式。

第二类斯特林数

定义 4 对于非负整数 \(a,b\)，第二类斯特林数 \(\begin{Bmatrix}a\\b\end{Bmatrix}\) 定义为将 \(n\) 个有标号小球放到 \(m\) 个无标号箱子（箱子不能为空）的方案数。

引理 5

\[ \begin{Bmatrix}a\\b\end{Bmatrix}=b\begin{Bmatrix}a-1\\b\end{Bmatrix}+\begin{Bmatrix}a-1\\b-1\end{Bmatrix},\quad a,b\ge 1\\[6pt] \begin{Bmatrix}a\\b\end{Bmatrix}=\frac{1}{b!}\sum_{i=1}^{b}(-1)^{b-i}\binom{b}{i}i^a=\sum_{i=1}^{b}\frac{(-1)^{b-i}i^a}{(b-i)!i!} \]

引理 6（拆幂）

\[ n^k=\sum_{i=1}^{n}\begin{Bmatrix}k\\i\end{Bmatrix}\binom{n}{i}i! \]

P2791 幼儿园篮球题

模板题。

CF1097G Vladislav and a Great Legend

请点击标题链接查看题解。

分拆数

表示 \(n\) 个无标号小球的无序划分方案数。我只会 \(O(n^2)\) 做法。

贝尔数

定义为斯特林数的一行之和，组合意义表示 \(n\) 个有标号小球的无序划分方案数。其 EGF 显然为 \(e^{e^x-1}\)。