组合数学基础

定义 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!} \]

\(\binom ab\) 在 \(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} \]

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

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

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

证明考虑枚举后缀极长连续段长度。

定理 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} \]

于是可以得到递推式。