求和式转化

在计数问题中我们经常需要对求和的式子进行转化来加速求和。这里略作整理。

基础-组合恒等式

• $\sum_{i=0}^{n}\binom{n}{i}=2^{n}$

• $\sum_{i=0}^{n}a^ib^{n-i}\binom{n}{i}=(a+b)^n$

  二项式定理。

• $\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}$

  当外层枚举的变量仅为 $j$ 时，我们可以利用这个恒等式将 $n,k$ 提出并把求和移到后面。后面的求和通常可以用 $(1)$ 式优化。

• $\sum_{i=0}^{n}\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}$

  当 $n,m,k$ 为常量时这个等式非常方便。

• $\binom{n}{m}m^{\underline{k}}=\binom{n-k}{m-k}n^{\underline{k}}$

  组合数也可以实现下降幂的转化。

基础-斯特林公式

• $n^m=\sum_{i=0}^{m}\binom{m}{i}\begin{Bmatrix}n\\i\end{Bmatrix}i!$

  注意到无论是斯特林数还是组合数当上面的数比下面的数大时均为 $0$ ，所以枚举的上界可以是 $n$ 也可以是 $m$ 。

• $\begin{Bmatrix}i\\j\end{Bmatrix}=\sum_{k=0}^{j}(-1)^{k+j}\binom{j}{k}k^i$

  拆斯特林数的方法。可以由 $(1)$ 二项式反演得到。

• $x^n=\sum_{i=0}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline{i}}\\ x^{\overline{n}}=\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i$

  斯特林数给我们提供了拆幂次项以及下降幂/上升幂/普通幂之间相互转化的工具。

技巧

• 当枚举的变量 $i$ 到某个值时，也许求和式中的斯特林数/排列组合数/上升下降幂就变为 $0$ 了，常用这点来修改上下边界。

• 任何的 $\sum$ 符号都是可以互换的（当然，你要确保每一层的上下界不变）。这一点非常重要。

  • 可以使本不在一个 $\sum$ 内的两个数乘到一起，再用恒等式变幻。
  • 可以将变量提出来，得到变量前的系数。
  • $\cdots$

• 当枚举的范围 $n$ 特别大 $(10^9)$ 时，并且式子中的幂次项的幂次范围不大时，可以考虑用斯特林公式。

• 利用斯特林公式可以实现普通幂/下降幂/上升幂多项式之间的转化。以普通幂转下降幂为例

  $F(x)=\sum_{i=0}^{n}a_ix^i=\sum_{i=0}^{n}a_i\sum_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}x^{\underline{j}}=\sum_{j=0}^{n}x^{\underline{j}}\sum_{i=j}^{n}a_i\begin{Bmatrix}i\\j\end{Bmatrix}$

  后面的 $\sum$ 即为系数

• 注意二项式定理的灵活运用。$(a+b)^n$ 中 $a,b$ 可以任意指定。

实战

• $\sum_{i=1}^{n}\binom{n}{i}i^k \pmod{10^9+7}$

  Hint：$1\leq n\leq 10^9,1\leq k\leq 10^3$

  思路： $n$ 范围比较大，但 $k$ 范围比较小，考虑用斯特林公式展开。

  $\sum_{i=1}^{n}\binom{n}{i}\sum_{j=0}^{i}\begin{Bmatrix}k\\j\end{Bmatrix}\binom{i}{j}j!$

  仔细观察，发现两个组合数很有特点，与 $(2)$ 形式一致。考虑交换求和符号

  $\begin{aligned} \sum_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum_{i=j}^{n}\binom{n}{i}\binom{i}{j}&=\sum_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum_{i=j}^{n}\binom{n}{j}\binom{n-j}{i-j}\\&=\sum_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}j!\binom{n}{j}\sum_{i=j}^{n}\binom{n-j}{i-j}\\&=\sum_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}j!\binom{n}{j}\sum_{i=0}^{n-j}\binom{n-j}{i}\\&=\sum_{j=0}^{k}\begin{Bmatrix}k\\j\end{Bmatrix}j!\binom{n}{j}2^{n-j} \end{aligned}$

  做完了。

• $\sum_{i=0}^{n}\sum_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}2^jj!$

  Hint：$1\leq n\leq 10^5$

  思路：这个式子平平无奇。我们尝试打开斯特林数让式子有趣一点。

  $\sum_{i=0}^{n}\sum_{j=0}^{i}2^jj!\sum_{k=0}^{j}(-1)^{k+j}\binom{j}{k}k^i$

  发现除了 $k^i$ 项以外所有的项都与 $i$ 无关。考虑将 $k$ 提前枚举，再把 $j$ 拆成卷积的形式。

  $\sum_{i=0}^{n}\sum_{k=0}^{n}\frac{k^i}{k!}\sum_{j=k}^{i}\frac{(-1)^{j-k}}{(j-k)!}\cdot\frac{j!2^j}{1}$

  注意到后面 $j$ 枚举的东西只与 $k$ 有关。不妨设为 $a_k$ 。

  $\sum_{i=0}^{n}\sum_{k=0}^{n}k^i\frac{a_k}{k!} =\sum_{k=0}^{n}\frac{a_k}{k!}\sum_{i=0}^{n}k^i=\sum_{k=0}^{n}\frac{a_k}{k!}\cdot\frac{k^{n+1}-1}{k-1}$

  $a_k$ 是可以用减法卷积求的。所以这个题就做完了。

• $\sum_{k=0}^{n}F(k)\times x^k\times \binom{n}{k} \pmod{p}$

  其中 $F(x)=\sum\limits_{i=0}^{m}a_ix^i$ 。

  Hint：$1\leq n,x,p\leq 10^9,1\leq m\leq 10^3$

  思路：看上去后面的东西与第一道例题很相似，我们尝试打开。

  $\sum_{k=0}^{n}F(k)\times \binom{n}{k}\sum_{i=0}^{k}\binom{x}{i}\begin{Bmatrix}k\\i\end{Bmatrix}i!$

  后面那两个组合数没有一个字母一样，显然不可做了。换个想法。拆普通幂的方法还有第二条斯特林公式。

  如果把多项式 $F(x)$ 带入 $k$ ，再放入求和式内，我们会得到

  $\sum_{k=0}^{n}\sum_{i=0}^{m}a_ik^i\times x^k\times \binom{n}{k}=\sum_{k=0}^{n}\sum_{i=0}^{m}\binom{n}{k}a_ik^i\times x^k=\sum_{i=0}^{m}a_i\sum_{k=0}^{n}\binom{n}{k}k^ix^k$

  内层的枚举中，各字母特点极似组合数乘下降幂的特点。

  根据技巧中的第四条将 $F(x)$ 转变为下降幂多项式 $F(x)=\sum\limits_{i=0}^{m}a_ix^i=\sum\limits_{i=0}^{m}b_ix^{\underline{i}}$ ，我们将 $x^{\underline{i}}$ 带进去试试。

  $\begin{aligned} \sum_{i=0}^{m}b_i\sum_{k=0}^{n}\binom{n}{k}k^{\underline{i}}x^k&=\sum_{i=0}^{m}b_in^{\underline{i}}\sum_{k=0}^{n}\binom{n-i}{k-i}x^k\\&=\sum_{i=0}^{m}x^ib_in^{\underline{i}}\sum_{k=0}^{n-i}\binom{n-i}{k}x^k\\&=\sum_{i=0}^{m}x^ib_in^{\underline{i}}(x+1)^{n-i} \end{aligned}$

  利用二项式定理成功将 $n$ 提到了指数上。