一个组合恒等式
liruixiong0101
·
·
算法·理论
介绍：
《具体数学》上提到了这样一个恒等式：
\sum_k{n\choose k}(-1)^k(a_0+a_1k+\cdots+a_nk^n)=(-1)^nn!a_n
一个多项式不同点值的组合等于一个很简单的式子，我一开始看到还是很惊讶的。而且如果这个多项式的次数小于 n，那么整个式子就等于 0！
接下来会讲这个式子的证明、推广与应用。
证明：
《具体数学》的推导方式：
首先我们定义差分算子 \Delta、位移算子 \text E 和恒等算子 1，满足：\Delta{f(x)}=f(x+1)-f(x),\text{E}f(x)=f(x+1),\text{1}f(x)=f(x)。
接下来定义 k 阶差分算子 \Delta^k 和 k 阶位移算子 \text{E}^k，满足：\Delta^kf(x)=\Delta(\Delta^{k-1}f(x)),\text{E}^kf(x)=\text{E}(\text{E}^{k-1}f(x))=f(x+k)。
我们来探究一下 k 阶差分的性质，我们列出下表。
\begin{align*}
\Delta f(x) &= f(x+1)-f(x) \\
\Delta^2 f(x) &= \Delta f(x+1)-\Delta f(x) \\
&= (f(x+2)-f(x+1))-(f(x+1)-f(x)) \\
&= f(x+2)-2f(x+1)+f(x) \\
\Delta^3 f(x) &= f(x+3)-3f(x+2)+3f(x+1)-f(x) \\
\Delta^4 f(x) &= f(x+4)-4f(x+3)+6f(x+2)-4f(x+1)+f(x)
\end{align*}
发现这个系数和二项式系数有点关系，事实上，如下式子成立：
\Delta^n f(x)=\sum_k{n\choose k}(-1)^{n-k}f(x+k)\tag{1}
其中 n 为非负整数。
这个式子容易用归纳法证明，但是用到初等算子理论会更加简单。
由于 \Delta f(x)=\text{E}f(x)-\text{1}f(x) 即 \Delta=\text{E}-\text{1}。
由二项式定理：
\Delta^n=(\text{E}-\text{1})^n=\sum_k{n\choose k}\text{E}^k(-\text{1})^{n-k}
同样可以证明。
接下来，我们考虑这个东西：
\Delta\left({x\choose m}\right)={x+1\choose m}-{x\choose m}={x\choose m-1}
牛顿发现了它，发现这个函数的 k 阶差分很好算，于是给出下面的极数：
f(x)=c_d{x\choose d}+c_{d-1}{x\choose d-1}+\cdots+c_1{x\choose 1}+c_0{x\choose 0}\tag{2}
我们称其为牛顿级数。
将其做 n 阶差分：
\Delta^nf(x)=c_d{x\choose d-n}+c_{d-1}{x\choose d-1-n}+\cdots+c_1{x\choose 1-n}+c_0{x\choose -n}=\sum_kc_k{x\choose k-n}
如果现在令 x=0，由于 {0\choose t}\neq 0 仅在 t=0 的情况下成立，所以我们可以得到：
\Delta^nf(0)=\left\{
\begin{aligned}
c_n,n\le d \\
0,n>d
\end{aligned}
\right.
为了方便我们就设：若 n\not\in\{0,1,\cdots,d\}，那么 c_n=0。所以 \Delta^nf(0)=c_n，这就免得分类讨论了。
那么我们可以将牛顿级数改写为：
f(x)=\Delta^df(0){x\choose d}+\Delta^{d-1}f(0){x\choose d-1}+\cdots+\Delta f(0){x\choose 1}+f(0){x\choose 0}\tag{3}
将组合数用下降幂展开，就和无限微积分中的麦克劳林级数类似了：
f(x)=\frac{\Delta^0f(0)}{0!}x^{\underline{0}}+\frac{\Delta^1f(0)}{1!}x^{\underline{1}}+\cdots+\frac{\Delta^{d-1}f(0)}{(d-1)!}x^{\underline{d-1}}+\frac{\Delta^df(0)}{d!}x^{\underline{d}}
g(x)=\frac{g^{(0)}(0)}{0!}x^0+\frac{g^{(1)}(0)}{1!}x^1+\cdots+\frac{g^{(d-1)}(0)}{(d-1)!}x^{d-1}+\frac{g^{(d)}(0)}{d!}x^d
接下来，我们对 (2) 式做 t 阶差分，并运用 (1) 式，再令 x=0，得：
\Delta^tf(0)=\sum_k{t\choose k}(-1)^{t-k}\left(c_0{k\choose 0}+c_1{k\choose 1}+\cdots+c_d{k\choose d}\right)=c_t
即：
\sum_k{t\choose k}(-1)^k\left(c_0{k\choose 0}+c_1{k\choose 1}+\cdots+c_d{k\choose d}\right)=(-1)^tc_t\tag{4}
这个式子的左边很复杂，右边却很简单。且若 t>d 整个式子的值为 0，这令人惊讶。
但是牛顿级数我们并不是特别常用，而是普通的多项式用的更多，我们将组合数中的下降幂转化成普通幂试试。
\begin{align*}
f(x) &= \sum_{j=0}^dc_j\frac{x^{\underline j}}{j!} \\
&= \sum_{j=0}^d\frac{c_j}{j!}\sum_{k=0}^j{j\brack k}(-1)^{j-k}x^k \\
&= \sum_{k=0}^dx^k\sum_{j=k}^d{j\brack k}(-1)^{j-k}\frac{c_j}{j!} \\
&= \sum_{k=0}^da_kx^k
\end{align*}
其中 a_k=\sum_{j=k}^d{j\brack k}(-1)^{j-k}\frac{c_j}{j!}，假如我们现在知道系数 a，我们可以通过反演求出 c，那么我们就可以顺利求出：
\sum_k{t\choose k}(-1)^k(a_0k^0+a_1k^1+\cdots+a_dk^d)
其实这就是斯特林反演，这里推一下。
先令 b_k=\frac{c_k}{k!}，那么条件变为：
a_k=\sum_{j=k}^d{j\brack k}(-1)^{j-k}b_j
接着直接斯特林反演：
\begin{align*}
b_k&=\sum_{i=k}^db_i[k=i] \\
&=\sum_{i=k}^db_i\sum_{j=k}^i(-1)^{i-j}{i\brack j}{j\brace k} \\
&=\sum_{j=k}^d{j\brace k}\sum_{i=j}^d(-1)^{i-j}{i\brack j}b_i \\
&=\sum_{j=k}^d{j\brace k}a_j
\end{align*}
中间用了斯特林数的反转公式进行恒等变换。
所以我们就有 c_k=k!\sum_{j=k}^d{j\brace k}a_j。
带入 (4)，得到：
\sum_k{t\choose k}(-1)^k(a_0k^0+a_1k^1+\cdots+a_dk^d)=(-1)^tt!\sum_{j=t}^d{j\brace t}a_j\tag{5}
在这里我们令 t\le k，就可以得到最开始给出的那个恒等式，令 t<k 就可以得到 (6)，令 t=k+1 就可以得到 (8)，读者可以自行推导一下。
\sum_k{d+1\choose k}(-1)^k(a_0k^0+a_1k^1+\cdots+a_dk^d)=0\tag{6}
\sum_k{d\choose k}(-1)^k(a_0k^0+a_1k^1+\cdots+a_dk^d)=(-1)^dd!a_d\tag{7}
\sum_k{d-1\choose k}(-1)^k(a_0k^0+a_1k^1+\cdots+a_dk^d)=(-1)^{d-1}(d-1)!(a_{d-1}+\frac{d(d-1)}{2}a_d)\tag{8}
另一种思考方式：
注意到第二类斯特林数的通项公式跟这个式子特别像：
{m\brace n}=\frac{(-1)^n}{n!}\sum_{k=0}^n(-1)^k{n\choose k}k^m\tag{9}
我们试试带数进去，首先我们带入 m=n，得到：
{n\brace n}=\frac{(-1)^n}{n!}\sum_{k=0}^n(-1)^k{n\choose k}k^n=1\Leftrightarrow\sum_{k=0}^n(-1)^k{n\choose k}k^n=(-1)^nn!
我们继续带入 m<n，那么 {m\brace n}=0，得到：
\sum_{k=0}^n(-1)^k{n\choose k}k^m=0
我们将这些等式分别乘以 a_m(0\le m\le n) 再累和就得到了：
\sum_k{n\choose k}(-1)^k(a_0k^0+a_1k^1+\cdots+a_nk^n)=(-1)^nn!a_n
这就是恒等式 (7)。
接着我们带入 m=n+1，此时 {m\brace n}=\frac{n(n+1)}{2}：
\sum_{k=0}^n(-1)^k{n\choose k}k^{n+1}=(-1)^nn!\frac{n(n+1)}2
同样地，我们可以推出恒等式 (8)。
我们换了一个方式思考，似乎毫不费力的就得到了恒等式 (6)(7)(8)。
《具体数学》的方法那个式子反演较为困难，我们换了一种思考方式也许更加简单。
我们可以考虑更复杂的情况，先将通项公式改写：
\sum_{k=0}^n(-1)^k{n\choose k}a_mk^m=(-1)^nn!{m\brace n}a_m
对 m 累和：
\sum_{k=0}^n(-1)^k{n\choose k}\sum_{i=0}^ma_ik^i=(-1)^nn!\sum_{i=0}^m{i\brace n}a_i
这其实就是 (5)，前面我们对 n 进行赋值，这里我们可以对 a 进行赋值，如果序列 a 有很好的性质的话，可以导出其他的恒等式。
这里留一道题目，求下面双重和式的封闭形式：
\sum_{i=0}^m(-1)^i{m\brack i}\sum_{j=0}^n(-1)^j{n\choose j}j^i
解法在「应用」里，往下翻就行了。
应用：
运用 (5)(6)(7)(8)，我们可以导出很多结论。
问题一：一个简单的经典的问题
求 \displaystyle\sum_{k=0}^n{n\choose k}(-1)^k 的封闭形式。
::::success[解法：]
设 a_k=[k=0]，套用 (7) 得到原式的值为 (-1)^nn!a_n=[n=0]。
::::
问题二：上一个问题的扩展
求 \displaystyle\sum_{k=0}^n{n\choose k}(-1)^kk 的封闭形式。
::::success[解法：]
当 n>1，套用 (6) 答案肯定为 0，当 n=0 时答案为 0，n=1 时答案为 -1。综上，这道题的答案为 -[n=1]。
::::
问题三：一个稍稍难一点的问题
求 \displaystyle\sum_{k=0}^n{n\choose k}(-1)^k(a+k)^n 的封闭形式。
::::success[解法：]
将 (a+k)^n 用二项式定理展开，其中 k^n 的系数为 1，直接套用 (7)，得到原式等于 (-1)^nn!
::::
问题四：一个看起来特别困难的问题
求 \displaystyle\sum_{k=0}^n{r-sk\choose k}{r-(s+1)k\choose n-k}(-1)^k 的封闭形式。
::::success[解法：]
这两个组合数相乘特别的刻意，思考后发现可以直接变成 \displaystyle{n\choose k}{r-sk\choose n}。
利用 \displaystyle{r-sk\choose n}=\dfrac{(r-sk)^{\underline n}}{n!} 将组合数展开，发现这个组合数相当于一个关于 k 的 n 次多项式，可以套用 (6)，现在我们只要求出 \dfrac{(r-sk)^{\underline n}}{n!} 的 k^n 项的系数即可。
容易得出系数为 \dfrac{(-s)^n}{n!}=(-1)^n\dfrac{s^n}{n!}，带入 (8) 得到原式的值为 (-1)^nn!(-1)^n\dfrac{s^n}{n!}=s^n。
::::
问题五：更加困难的问题
求 \displaystyle\sum_{i=1}^ni^n\sum_{j=i}^n{n\choose j}(-1)^{n-j} 的封闭形式。
::::success[解法：]
先将 (-1)^n 提出。
我们发现这个形式不是我们想要的形式，我们想要将 \displaystyle{n\choose j}(-1)^j 提到第一重和式的位置，所以我们将 i,j 这两重和式交换，得到原式等于 \displaystyle(-1)^n\sum_{k=0}^n{n\choose k}(-1)^k\sum_{i=1}^ki^n（写成 k 更习惯）。
然后就很好做了，熟知 \displaystyle\sum_{i=1}^ki^n 的封闭形式是一个关于 k 的 n+1 次多项式，所以现在就可以套用 (8) 了，现在只需要求出这个多项式的 k^{n+1} 和 k^n 系数就可以了。
我们可以通过用伯努利数来求出系数，这里省略过程只给结果：
- 当 n=0 时：k^{n+1} 系数为 1，k^n 系数为 0。
- 当 n\neq 0 时：k^{n+1} 和 k^n 系数分别为 \frac{1}{n+1},\frac 12。
先不考虑 n=0 的情况，我们令 d=n+1,a_d=\frac{1}{n+1},a_{d-1}=\frac 12，带入 (8)，可以得到原式等于 \frac{(n+1)!}2。
当 n=0 时，答案为 0，需要特殊判断。所以我们得出最终的答案为：
\frac{(n+1)!}2[n>0]
::::
问题六：原来留下来的题目
求 \displaystyle\sum_{i=0}^m(-1)^i{m\brack i}\sum_{j=0}^n(-1)^j{n\choose j}j^i 的封闭形式。
::::success[解法：]
同样的将 i,j 交换，得到 \displaystyle\sum_{k=0}^n(-1)^k{n\choose k}\sum_{i=0}^m(-1)^i{m\brack i}k^i。我们想要套用 (5)，于是我们令 a_i=(-1)^i{m\brack i}，将其带入 (5) 右边：
(-1)^nn!\sum_{i=0}^m(-1)^i{m\brack i}{i\brace n}=n!\sum_{i=0}^m(-1)^{n-i}{m\brack i}{i\brace n}
这显然是斯特林数的反转公式，那么他就等于 n![n=m]。
所以最终的答案就是 n![n=m]
::::
类似的恒等式还有：
\sum_{i=0}^m{m\choose i}\sum_{j=0}^n(-1)^j{n\choose j}j^i=(-1)^nn!{m+1\brace n+1}
\sum_{i=0}^m(n+1)^{m-i}\sum_{j=0}^n(-1)^j{n\choose j}j^i=(-1)^nn!{m+1\brace n+1}
\sum_{i=0}^m(-1)^i{m+1\brack i+1}\sum_{j=0}^n(-1)^j{n\choose j}j^i=m![m\ge n]
这里的问题都是用了上面的结论证明出来的，如果有不用上面结论证明出来的，欢迎在讨论区分享，或私信。（问题一，问题二这种简单题就没必要了）