下降幂学习笔记
还原精灵还我笔记——来自打完笔记但关电脑前没有保存的某人的呐喊。
定义
下降幂就是形如 \(n^{\underline{m}}\) 的式子，表示
\[n^{\underline{m}}=\prod_{i=n-m+1}^{n}=\frac{n!}{(n-m)!} \]同理声明一个上升幂 \(n^{\overline{m}}\)，表示
\[n^{\overline{m}}=\prod_{i=n}^{n+m-1}i=\frac{(n+m-1)!}{(n-1)!} \]注意这里 \(n,m\) 均可以取负数即可。
性质
上升下降之间的转换
首先是幂相加的求解
\[n^{\underline{a+b}}=n^{\underline{a}}(n-a)^{\underline{b}}\\ n^{\overline{a+b}}=n^{\overline{a}}(n+a)^{\overline{b}} \]这个性质常用于倍增求解一些多项式，因为有
\[x^{\underline{2n}}=x^{\underline{n}}(x-n)^{\underline{n}}\\ x^{\underline{2n+1}}=x^{\underline{2n}}(x-2n) \]这样良好的性质，于是可以设 \(x^{\underline{n}}=f(x)=\sum_{i=0}^{n}a_ix^i\)，则有
\[\begin{aligned}x^{\underline{2n}}&=f(x)f(x-n)\\&=(\sum_{i=0}^{n}a_ix^i)(\sum_{i=0}^{n}a_i(x-n)^i)\\&=(\sum_{i=0}^{n}a_ix^i)(\sum_{i=0}^{n}a_i\sum_{j=0}^{i}\binom{i}{j}x^j(-n)^{i-j})\\&=(\sum_{i=0}^{n}a_ix^i)(\sum_{j=0}^{n}x_j\sum_{i=j}^{n}a_i\binom{i}{j}(-n)^{i-j})\\&=(\sum_{i=0}^{n}a_ix^i)(\sum_{j=0}^{n}x^j\sum_{i=j}a_i(-n)^{i-j}\frac{i!}{j!(i-j)!})\\&=(\sum_{i=0}^{n}a_ix^i)(\sum_{i=0}^{n}\frac{x^i}{i!}\sum_{j=i}^{n}(a_jj!)\frac{(-n)^{j-i}}{(j-i)!}) \end{aligned} \]于是可以设 \(F_i=a_ii!,G_i=\frac{(-n)^{i}}{i!},G'_i=G_{n-i}\)。那么原式等于
\[\begin{aligned}&=(\sum_{i=0}^{n}a_ix^i)(\sum_{i=0}^{n}\frac{x^i}{i!}\sum_{j=i}^{n}F_jG_{j-i})\\&=(\sum_{i=0}^{n}a_ix^i)(\sum_{i=0}^{n}\frac{x^i}{i!}\sum_{j=i}^{n}F_jG'_{n-(j-i)}) \end{aligned} \]如果令 \(W_i=(FG')_i\)，则原式等于
\[\begin{aligned}&=(\sum_{i=0}^{n}a_ix^i)(\sum_{i=0}^{n}\frac{W_{n+i}}{i!}x^i)\end{aligned} \]于是转换成两个多项式相乘，依旧利用 \(\text{FFT}\) 求解即可。于是我们便能在
\[T(n)=T(\frac{n}{2})+O(n\log n)=O(n\log n) \]的时间复杂度内，得到 \(x^{\underline{n}}\) 的展开形式，上升幂同理。
接着有
\[n^{\underline{m}}=(-1)^m(-n)^{\overline{m}}=(n-m+1)^{\overline{m}}\\ n^{\overline{m}}=(-1)^m(-n)^{\underline{m}}=(n+m-1)^{\underline{m}} \]关于组合数
下降幂和组合数结合往往有意想不到的效果。
首先先简单将组合数转化成下降幂的形式
\[\binom{n}{m}=\frac{n!}{m!(n-m)!}=\frac{n^{\underline{m}}}{m!} \]这个性质可以将组合数拓展到实数域
\[\binom{r}{n}=\frac{r^{\underline{n}}}{n!} \]此处的 \(r\) 是任意实数。然后可以用这个表示牛顿二项式定理
\[(x+y)^r=\sum_{i\ge 0}\binom{r}{i}x^iy^{r-i} \]只需要注意 \(i\) 没有上界即可。二项式定理其实是 \(r\) 取任意非负整数时的特殊情况，因为当 \(i>r\) 时，\(\binom{r}{i}\equiv 0\)，因此省略了后面的无穷项。
然后有一个组合数的转换
\[\binom{n}{m}=\frac{n^{\underline{m}}}{m!}=\frac{(-1)^m(-n)^{\overline{m}}}{m!}=(-1)^m\frac{(m-n-1)^{\underline{m}}}{m!}=(-1)^m\binom{m-n-1}{m} \]接着考虑下降幂与组合数相乘
\[\binom{n}{k}k^{\underline{i}}=\frac{n!}{k!(n-k)!}\frac{k!}{(k-i)!}=\frac{(n-i)!}{(n-k)!(k-i)!}\frac{n!}{(n-i)!}=\binom{n-i}{k-i}n^{\underline{i}} \]通过这个性质，不妨将 \(n,i\) 视作参数，那么我们成功将变化的 \(k^{\underline{i}}\) 转换成了不变的 \(n^{\underline{i}}\)，那么预处理将会容易许多。
更常见的，对于多项式乘组合数的情况，即 \(f(k)\binom{n}{k}\) 的形式，不难考虑到将 \(f(x)=\sum_{i\ge 0}a_ix^i\) 的形式改写成 \(f(x)=\sum_{i\ge 0}b_ix^{\underline{i}}\) 的形式，那么则有
\[\begin{aligned}f(k)\binom{n}{k}&=\binom{n}{k}\sum_{i\ge 0}b_ik^{\underline{i}}\\&=\sum_{i\ge 0}b_ik^{\underline{i}}\binom{n}{k}\\&=\sum_{i\ge 0}b_i\binom{n-i}{k-i}n^{\underline{i}} \end{aligned} \]于是我们看出来只需要求出 \(b_i\)，便能求出整个表达式的值。
于是我们考虑
\[x^n=\sum_{x=1}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}i!\binom{x}{i}=\sum_{x=1}^{n}\begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline{i}} \]考虑组合意义，即 \(n\) 个不同的球放进 \(x\) 个不同的盒子里，盒子可以为空。那么就是枚举具体放进了多少个盒子，从 \(x\) 个盒子中选出来，将 \(n\) 个球放入有多少方案，接着考虑不同的盒子，因此需要乘上 \(i!\)。
那么有
\[\begin{aligned}f(x)&=\sum_{i\ge 0}a_ix^i\\&=\sum_{i\ge 0}a_i\sum_{j=0}^{i}\begin{Bmatrix}i\\j\end{Bmatrix}x^{\underline{j}}\\&=\sum_{i\ge 0}x_i\sum_{j\ge i}a_j\begin{Bmatrix}i\\j\end{Bmatrix} \end{aligned} \]所以有 \(b_i=\sum_{j\ge i}a_j\begin{Bmatrix}j\\i\end{Bmatrix}\)，预处理第二类斯特林数可以对于 \(n\) 次多项式做到 \(O(n^2)\) 求解。
接着考虑一个推导：求 \(F(x)=\sum_{i\ge 0}\binom{2i}{i}x^i\) 的封闭形式。
首先有一个显然成立的等式
\[x^{\underline{k}}(x-\frac{1}{2})^{\underline{k}}=\frac{(2x)^{\underline{2k}}}{2^{2k}} \]其实只需要将左边展开后每一项均乘 \(2\) 即可得到。那么就有
\[\begin{aligned}\binom{2n}{n}&=\frac{(2n)^{\underline{n}}}{n!}\\&=\frac{(2n)^{\underline{2n}}}{(n!)^2}\\&=\frac{2^{2n}n^{\underline{n}}(n-\frac{1}{2})^{\underline{n}}}{(n!)^2}\\&=(2^2)^n\frac{(n-\frac{1}{2})^{\underline{n}}}{n!}\\&=4^n\binom{n-\frac{1}{2}}{n}\\&=4^n(-1)^n\binom{n-(n-\frac{1}{2})-1}{n}\\&=(-4)^n\binom{-\frac{1}{2}}{n} \end{aligned} \]所以
\[\begin{aligned}F(x)&=\sum_{i\ge 0}\binom{2i}{i}x^i\\&=\sum_{i\ge 0}(-4)^i\binom{-\frac{1}{2}}{i}x^i\\&=\sum_{i\ge 0}(-4x)^i\binom{-\frac{1}{2}}{i}\\&=(1-4x)^{-\frac{1}{2}}\\&=\frac{1}{\sqrt{1-4x}} \end{aligned} \]
对于下降幂也有二项式定理
\[(x+y)^{\underline{n}}=\sum_{i=0}^{n}\binom{n}{i}x^{\underline{i}}y^{\underline{n-i}}\\(x+y)^{\overline{n}}=\sum_{i=0}^{n}\binom{n}{i}x^{\overline{i}}y^{\overline{n-i}}\\ \]考虑证明：
\[\begin{aligned}\sum_{i=0}^{n}\binom{n}{i}x^{\underline{i}}y^{\underline{n-i}}&=\sum_{i=0}^{n}\frac{n!}{i!(n-i)!}x^{\underline{i}}y^{\underline{n-i}}\\&=n!\sum_{i=0}^{n}\binom{x}{i}\binom{y}{n-i}\\&=n!\binom{x+y}{n}\\&=(x+y)^{\underline{n}} \end{aligned} \]考虑组合意义，\(\binom{x}{i}\binom{y}{n-i}\) 就表示从 \(x+y\) 个中选出 \(n\) 个的方案数。上升幂相关的证明同理。
有限微积分
重定义
在微积分中我们引入了算子 \(D\) 的概念，表示一个无穷小量上的斜率
\[Df(x)=\frac{df(x)}{dx}=\lim_{h\to 0}\frac{f(x+h)-f(x)}{h} \]此时我们定义另一个算子 \(\Delta\) 表示 \(h=1\) 时的斜率，也就是
\[\Delta f(x)=f(x+1)-f(x) \]本质上就是差分。
在 \(D\) 算子下，最基本的函数是
\[Dx^m=mx^{m-1} \]但在 \(\Delta\) 算子下，\((x+1)^m-x^m\)，没什么能够化简的地方，于是我们考虑下降幂
\[\Delta x^{\underline{m}}=(x+1)^{\underline{m}}-x^{\underline{m}}=mx^{\underline{m-1}} \]我们发现这和上面的形式一样。
接着考虑无限微积分上定义积分
\[g(x)=Df(x)\Leftrightarrow\int g(x)dx=f(x)+C \]类似的，我们也可以定义
\[g(x)=\Delta f(x)\Leftrightarrow\sum g(x)\delta x=f(x)+C \]这个 \(C\) 只需要满足在差分后能够消掉，即周期为 \(1\) 的函数。
类似定义定积分
\[\int_{a}^{b}g(x)dx=f(x)\mid_{a}^{b}=f(b)-f(a)\\ \sum_{a}^{b}g(x)\delta x=f(x)\mid_{a}^{b}=f(b)-f(a)=\sum_{i=a}^{b-1}g(i) \]根据定积分的性质，同样的，定义
\[\sum_{a}^{b}g(x)\delta x=-\sum_{b}^{a}g(x)\delta x\\ \sum_{a}^{b}g(x)\delta x+\sum_{b}^{c}g(x)\delta x=\sum_{a}^{c}g(x)\delta x \]函数的对应关系
对 \(x^{\underline{m}}\) 进行积分，得
\[\sum_{i=0}^{n-1}i^{\underline{m}}=\frac{i^{\underline{m+1}}}{m+1}\mid_{0}^{n}=\frac{n^{\underline{m+1}}}{m+1} \]可惜当 \(m=-1\) 时无法使用，于是当 \(m=-1\) 时我们暴力展开，有
\[\sum_{i=0}^{n-1}i^{\underline{m}}=\sum_{i=1}^{n}\frac{1}{i}=H_n \]所以我们知道
\[\sum x^{\underline{m}}\delta x=\left\{\begin{matrix}\frac{x^{\underline{m+1}}}{m+1}+C&m\ne 1\\H_x+C&m=1\end{matrix} \right . \]联想到 \(\int x^{-1}dx=\ln x+C\)，于是我们找到了能和 \(\ln x\) 相互对应的函数 \(H_x=\sum_{i=1}^{x}\frac{1}{i}\)。
考虑无限微积分中的 \(De^x=e^x\)，找到一个类似的函数，不难发现 \(\Delta2^x=2^x\)。考虑对于所有 \(a^x\) 的差分和逆差分，有
\[\Delta f(x)=a^{x+1}-a^x=(a-1)a^x\\ \sum f(x)\delta x=\frac{a^x}{a-1} \]更进一步，令 \(\Delta_k f(x)=f(x+k)-f(x)\)，同样试图找到一个函数 \(a^x\)，满足 \(e^x\) 的性质，于是有
\[\begin{aligned}&\frac{a^{x+k}-a^x}{k}=a^x\\\Rightarrow&a^k-1=k\\\Rightarrow&a=\sqrt[k]{k+1}\end{aligned} \]那么当 \(\lim_{k\to 0}\)，有
\[e=\lim_{k\to 0}(k+1)^{\frac{1}{k}}=\lim_{n\to\infin}(1+\frac{1}{n})^n \]运算法则
显然有 \(\Delta(f+g)=\Delta f+\Delta g,\Delta(cg)=c\Delta g\)，\(c\) 是常数。
接着考虑乘法运算，则有
\[\begin{aligned}\Delta(f(x)g(x))&=f(x+1)g(x+1)-f(x)g(x)\\&=f(x+1)g(x+1)-f(x+1)g(x)-f(x)g(x)+f(x+1)g(x)\\&=f(x+1)\Delta g(x)+g(x)\Delta f(x) \end{aligned} \]定义位移算子 \(E(f(x))\) 表示 \(f(x+1)\)，则有
\[\Delta fg=Ef\Delta g+g\Delta f \]对两边同时逆差分后可以得到
\[\sum g\Delta f=fg-\sum Ef\Delta g \]考虑利用有限微积分计算的具体的问题。
-
求 \(\sum_{k=0}^{n-1}k^2\)。
将 \(k^2\) 拆成 \(k^{\underline{2}}+k^{\underline{1}}\)，那么因为 \(\sum_{i=0}^{n-1}i^{\underline{m}}=\frac{n^{\underline{m+1}}}{m+1}\) 可以得到
\[\begin{aligned}\sum_{k=0}^{n-1}k^2&=sum_{k=0}^{n-1}(k^{\underline{2}}+k^{\underline{1}})\\&=\sum_{k=0}^{n-1}k^{\underline{2}}+\sum_{k=0}^{n-1}k^{\underline{1}}\\&=\frac{n^{\underline{3}}}{3}+\frac{n^{\underline{2}}}{2}\end{aligned} \]展开后化简可以得到我们日常使用的公式
\[\sum_{k=0}^{n-1}k^2=\frac{n(n-1)(2n-1)}{6} \]事实上，通过斯特林数，很多时候一般幂和下降幂间转化。
-
求 \(\sum_{k=0}^{n}k2^k\)。
我们想利用上面的公式，不妨令 \(\Delta f(x)=2^x,g(x)=x\)，则有 \(f(x)=2^x,\Delta g(x)=1\)。那么所求即为 \(\sum_{i=0}^{n}g(k)\Delta f(k)=\sum_{i=0}^{n+1}g(k)\Delta f(k)\delta k\)。
定义 \(F(k)=\sum g(k)\Delta f(k)\delta k\)，则所求即为 \(F(k)\mid_{0}^{n+1}\)，于是考虑计算 \(F(k)\)，有
\[\begin{aligned}F(k)&=\sum g(k)\Delta f(k)\delta k\\&=f(k)g(k)-\sum E(f(k))\Delta g(k)\delta k\\&=k2^k-\sum 2^{k+1}\delta k\\&=k2^k-2^{k+1}\end{aligned} \]所以
\[\begin{aligned}F(k)\mid_{0}^{n+1}&=F(n+1)-F(0)\\&=((n+1)2^{n+1}-2^{n+2})-(02^0-2^{1})\\&=(n-1)2^{n+1}+2 \end{aligned} \]即
\[\sum_{k=0}^{n}k2^k=(n-1)2^{n+1}+2 \] -
求 \(\sum_{i=0}^{n-1}H_i\)。
依旧考虑相同的思路，但是不难发现我们难以对 \(H_x\) 进行逆差分，但是我们知道 \(H_x\) 的差分，于是应该令 \(\Delta f(x)=1,g(x)=H_x\)，则有 \(f(x)=x,\Delta g(x)=x^{\underline{-1}}\)。那么所求即为 \(\sum_{i=0}^{n-1}g(i)\Delta f(i)=\sum_{i=0}^{n}g(i)\Delta f(i)\delta i\)。定义 \(F(i)=\sum g(i)\Delta f(i)\delta i\)，则所求即为 \(F(i)\mid_{0}^{n}\)，考虑计算 \(F(i)\)，有
\[\begin{aligned}F(i)&=\sum g(i)\Delta f(i)\delta i\\&=f(i)g(i)-\sum E(f(i))\Delta g(i)\delta i\\&=iH_i-\sum (i+1)i^{\underline{-1}}\delta i\\&=iH_i-i \end{aligned} \]于是
\[\begin{aligned}F(i)\mid_{0}^{n}&=F(n)-F(0)\\&=(nH_n-n)-(0H_0-0)\\&=nH_n-n \end{aligned} \]即
\[\sum_{i=0}^{n-1}H_i=nH_n-n \] -
求 \(\sum_{i=0}^{n-1}kH_k\)。
事实上，根据前面的思路，这没有什么难的。
令 \(\Delta f(x)=x=x^{\underline{1}},g(x)=H_x\)，则 \(f(x)=\frac{x^{\underline{2}}}{2},\Delta g(x)=x^{\underline{-1}}\)。则所求即为 \(\sum_{i=0}^{n-1}g(i)\Delta f(i)=\sum_{i=0}^{n}g(i)\Delta f(i)\delta i\)。定义 \(F(i)=\sum g(i)\Delta f(i)\delta i\)，则所求即为 \(F(i)\mid_{0}^{n}\)，考虑计算 \(F(i)\)，有
\[\begin{aligned}F(i)&=\sum g(i)\Delta f(i)\delta i\\&=f(i)g(i)-\sum E(f(i))\Delta g(i)\delta i\\&=\frac{i^{\underline{2}}H_i}{2}-\sum\frac{(i+1)^{\underline{2}}}{2}i^{\underline{-1}}\delta i\\&=\frac{i^{\underline{2}}H_i}{2}-\sum \frac{i^{\underline{1}}}{2}\delta i\\&=\frac{i^{\underline{2}}H_i}{2}-\frac{i^{\underline{2}}}{4}\\&=\frac{i^{\underline{2}}(2H_i-1)}{4} \end{aligned} \]则
\[\begin{aligned}F(i)\mid_{0}^{n}&=F(n)-F(0)\\&=\frac{n^{\underline{2}}(2H_n-1)}{4}-\frac{0^{\underline{2}}(2H_0-1)}{4}\\&=\frac{n^{\underline{2}}(2H_n-1)}{4} \end{aligned} \]化成正常形式可以得到
\[\sum_{i=0}^{n-1}kH_k=\frac{n(n-1)(2H_n-1)}{4} \]