处理技巧

折半

加倍公式

rk(r12)k=(2r)2k/22k,k0\displaystyle r^{\underline{k}} \left(r - \frac{1}{2} \right) ^{\underline{k}} = (2r)^{\underline{2k}} / 2^{2k}, \quad k \geqslant 0

证明很简单,直接展开就可以,下面看几个推广

(1)\textbf{(1)}

(rk)(r1/2k)=(2r2k)(2kk)/22k,kZ\displaystyle \binom{r}{k} \binom{r-1/2}{k} = \binom{2r}{2k} \binom{2k}{k} / 2^{2k}, \quad k \in \mathbb{Z}

证明方法,在加倍公式的两边同时除以 (k!)2(k!)^2

(2)\textbf{(2)}

(n1/2n)=(2nn)/22n\displaystyle \binom{n - 1/2}{n} = \binom{2n}{n} / 2^{2n}

(1)\textbf{(1)} 中令 r=k=nr = k = n 即可

(3)\textbf{(3)}

(1/2n)=(14)n(2nn),nZ\displaystyle \binom{-1/2}{n} = \left(\frac{-1}{4} \right)^n \binom{2n}{n}, \quad n \in \mathbb{Z}

(2)\textbf{(2)} 反转上指标即可

(4)\textbf{(4)}

(1)\textbf{(1)} 中令 r=12n\displaystyle r = \frac{1}{2} n,可以得出

k(n2k)(2kk)22k=k(n/2k)((n1)/2k)=(n1/2n/2)\displaystyle \sum_k \binom{n}{2k} \binom{2k}{k} 2^{-2k} = \sum_k \binom{n/2}{k} \binom{(n-1)/2}{k} = \binom{n-1/2}{\left\lfloor n/2 \right\rfloor}

最后一步用了范德蒙卷积推广 (1)\textbf{(1)}

(5)\textbf{(5)}

k(2kk)(2n2knk)=4n,n0\displaystyle \sum_{k} \binom{2k}{k} \binom{2n-2k}{n-k} = 4^n, \quad n \geqslant 0

实际上,根据推广 (3)\textbf{(3)},可以得到

(1/2k)(1/2nk)=(14)k(2kk)(14)nk(2(nk)nk)\displaystyle \binom{-1/2}{k} \binom{-1/2}{n-k} = \left(\frac{-1}{4} \right)^{k} \binom{2k}{k} \cdot \left(\frac{-1}{4} \right)^{n-k} \binom{2(n-k)}{n-k}

=(1)n4n(2kk)(2n2knk)\displaystyle = \frac{(-1)^n}{4^n} \binom{2k}{k} \binom{2n-2k}{n-k}

根据范德蒙卷积

k(1/2k)(1/2nk)=(1n)=(1)n\displaystyle\sum_{k} \binom{-1/2}{k} \binom{-1/2}{n-k} = \binom{-1}{n} = (-1)^n

在推广 (3)\textbf{(3)} 的结果基础上,两边同时对 kk 求和,即可证明

差分

差分用来计算 (nk)(1)k\displaystyle \binom{n}{k}(-1)^k 的部分和

Δf(x)=f(x+1)f(x)\Delta f(x) = f(x+1) - f(x)

一般来说,nn 阶差分是

Δnf(x)=k(nk)(1)nkf(x+k),n0\Delta^n f(x) = \sum_{k} \binom{n}{k} (-1)^{n-k} f(x+k), \quad n \geqslant 0

证明如下,定义算子 Ef(x)=f(x+1)Ef(x) = f(x+1),算子 Δ=E1\Delta = E - 1

Δn=(E1)n=k(nk)Ek(1)nk\displaystyle \Delta^n = (E-1)^n = \sum_k \binom{n}{k} E^k (-1)^{n-k}EkE^k 即为 f(x+k)f(x+k)

对于负的下降幂

f(x)=(x1)1=1xf(x) = (x-1)^{\underline{-1}} = \frac{1}{x}

举几个例子,Δ2f(x)=(1)(2)(x1)3\displaystyle \Delta^2 f(x) = (-1)(-2) (x-1)^{\underline{-3}}

对于 nn 阶差分,有一般性公式

Δn((x1)1)=(1)n(x1)n1=(1)nn!x(x+1)(x+n)\displaystyle \Delta^n \left((x-1)^{\underline{-1}} \right) = (-1)^{\underline{n}} (x-1)^{\underline{-n-1}} = (-1)^n \frac{n!}{x(x+1)\cdots (x+n)}

根据差分展开式

k(nk)(1)kx+k=(1)nΔn(1x)=n!x(x+1)(x+n)=x1(x+nn)1,x{0,1,,n}\displaystyle \sum_{k} \binom{n}{k} \frac{(-1)^k}{x+k} = (-1)^n \Delta^n \left(\frac{1}{x} \right) = \frac{n!}{x(x+1)\cdots (x+n)} = x^{-1} \binom{x+n}{n}^{-1}, \quad x \notin \{0, -1, \cdots, -n\}

多项式差分

对于一般 dd 次多项式,f(x)=adxd+ad1xd1++a1x1+a0x0\displaystyle f(x) = a_d x^d + a_{d-1} x^{d-1} + \cdots + a_1x^1 + a_0 x^0

一般来说可以将其表示成为下降幂的和x2=x2+x1x^{2} = x^{\underline{2}} + x^{\underline{1}},从而有

f(x)=bdxd+bd1xd1++b1x1+b0x0\displaystyle f(x) = b_d x^{\underline{d} } + b_{d-1}x^{\underline{d-1}} + \cdots + b_1x^{\underline{1}} + b_0 x^{\underline{0}}

实际上,bd=ad,b0=a0b_d = a_d, b_0 = a_0,对于 0kd0 \leqslant k \leqslant d,令 ck=k!bkc_k = k! \cdot b_k,那么有

f(x)=cd(xd)+cd1(xd1)++c1(x1)+c0(x0)\displaystyle f(x) = c_d \binom{x}{d} + c_{d-1} \binom{x}{d-1} + \cdots + c_1 \binom{x}{1} + c_0 \binom{x}{0}

根据加法公式,可以推出 Δ((xk))=(xk1)\displaystyle \Delta \left(\binom{x}{k} \right) = \binom{x}{k-1}

牛顿级数的 nn 阶差分可以表示为

Δnf(x)=cd(xdn)+cd1(xd1n)++c1(x1n)+c0(xn)\displaystyle\Delta^n f(x) = c_d \binom{x}{d-n} + c_{d-1} \binom{x}{d-1-n} + \cdots + c_1 \binom{x}{1-n} + c_0 \binom{x}{-n}

对于 ck(xkn)\displaystyle c_k \binom{x}{k - n},令 x=0x = 0,只有 cnc_n 这一项

Δnf(0)={cnnd0n>d\displaystyle \Delta^n f(0) = \begin{cases} c_n & n \leqslant d \\ 0 & n > d \end{cases}

f(x)f(x)牛顿级数

f(x)=Δdf(0)(xd)+Δd1f(0)(xd1)++Δf(0)(x1)+f(0)(x0)\displaystyle f(x) = \Delta^d f(0) \binom{x}{d} + \Delta^{d-1} f(0) \binom{x}{d-1} + \cdots + \Delta f(0) \binom{x}{1} + f(0) \binom{x}{0}

实际上,对 x=0x = 0 应用 nn 阶差分的一般表达式,(1)nΔnf(0)=(1)ncn\displaystyle (-1)^n \Delta^n f(0) = (-1)^n c_n,可以推出

(1)ncn=k(nk)(1)k(f(k))\displaystyle (-1)^nc_n = \sum_{k} \binom{n}{k} (-1)^k \left(f(k) \right)

k(nk)(1)k(c0(k0)+c1(k1)+c2(k2)+)=(1)ncn,n0\displaystyle \sum_k \binom{n}{k} (-1)^k \left(c_0 \binom{k}{0} + c_1 \binom{k}{1} + c_2 \binom{k}{2} + \cdots \right) = (-1)^nc_n, \quad n \geqslant 0

实际上,多项式 a0+a1x+a2x2+anxn\displaystyle a_0 + a_1x + a_2 x^2 + \cdots a_nx^n 总可以写成牛顿级数 c0(x0)+c1(x1)++cn(xn)\displaystyle c_0 \binom{x}{0} + c_1 \binom{x}{1} + \cdots + c_n \binom{x}{n}
cn=n!anc_n = n!a_n,得到恒等式

k(nk)(1)k(a0+a1k+ankn)=(1)nn!an\displaystyle \sum_k \binom{n}{k} (-1)^k \left(a_0 + a_1k + \cdots a_nk^n \right) = (-1)^n n!a_n

差分的应用

牛顿级数
一般牛顿级数,根据之前的分析,Δnf(0)=cn\displaystyle \Delta^n f(0) = c_n,可以得到恒等式

f(x)=f(0)(x0)+Δf(0)(x1)+Δ2f(0)(x2)+Δ3f(0)(x3)+\displaystyle f(x) = f(0) \binom{x}{0} + \Delta f(0) \binom{x}{1} + \Delta^2 f(0) \binom{x}{2} + \Delta^3 f(0) \binom{x}{3} + \cdots

类似泰勒级数,f(x)=g(a+x)f(x) = g(a+x) 的牛顿级数可以写成

g(a+x)=g(a)0!x0+Δg(a)1!x1+Δ2g(a)2!x2+Δ3g(a)3!x3+g(a+x) = \frac{g(a)}{0!} x^{\underline{0}} + \frac{\Delta g(a)}{1!} x^{\underline{1}} + \frac{\Delta^2 g(a)}{2!} x^{\underline{2}} + \frac{\Delta^3 g(a)}{3!} x^{\underline{3}} + \cdots

证明很简单,因为 f(x)=g(a+x)f(x) = g(a+x),对于 n0n \geqslant 0Δnf(0)=Δng(a)\Delta^n f(0) = \Delta^n g(a)

举个例子,不妨设 g(x)=(1+z)xg(x) = (1+z)^x,如果 z<1|z| < 1,那么 Δg(x)=(1+z)x+1(1+z)x=z(1+z)x\displaystyle \Delta g(x) = (1+z)^{x+1} - (1+z)^x = z(1+z)^x
所以有 Δng(x)=zn(1+z)x\displaystyle \Delta^n g(x) = z^n (1+z)^x

g(a+x)=nΔng(a)(xn)=(1+z)an(xn)zn\displaystyle g(a+x) = \sum_n \Delta^n g(a) \binom{x}{n} = (1+z)^a \sum_n \binom{x}{n} z^n

以上结果收敛于 (1+z)a+x(1+z)^{a+x}

斯特林阶乘推广
根据牛顿级数,令 lnx!=nsn(xn)=s0(x0)+s1(x1)+s2(x2)+\displaystyle \ln x! = \sum_n s_n \binom{x}{n} = s_0 \binom{x}{0} + s_1 \binom{x}{1} + s_2 \binom{x}{2} + \cdots

现在 Δ(lnx!)=ln(x+1)!lnx!=ln(x+1)\Delta (\ln x!) = \ln (x+1)! - \ln x! = \ln (x+1),记 f(x)=ln(x+1)f(x) = \ln (x+1),根据差分展开

sn=Δn(lnx!)x=0\displaystyle s_n = \Delta^n (\ln x!) \big|_{x = 0}
 =Δn1(ln(x+1))x=0\displaystyle \quad \ = \Delta^{n-1} \left (\ln (x+1) \right) \big|_{x = 0}

 =k(n1k)(1)n1kf(0+k)=k(n1k)(1)n1kln(k+1)\displaystyle \quad \ = \sum_k \binom{n-1}{k} (-1)^{n-1-k} f(0+k) = \sum_k \binom{n-1}{k} (-1)^{n-1-k} \ln (k+1)

由此可以代入,举个例子,s4=ln43ln3+3ln2s_4 = \ln 4 - 3\ln 3 + 3 \ln 2

反演

反演公式

g(n)=k(nk)(1)kf(k)  f(n)=k(nk)(1)kg(k)g(n) = \sum_k \binom{n}{k} (-1)^k f(k) \ \Longleftrightarrow \ f(n) = \sum_k \binom{n}{k} (-1)^k g(k)

证明如下,实际上,我们需要求 k(nk)(1)kg(k)\displaystyle \sum_k \binom{n}{k} (-1)^k g(k)

而对 k0k \geqslant 0,我们有 g(k)=j(kj)(1)jf(j)\displaystyle g(k) = \sum_j \binom{k}{j} (-1)^j f(j)

k(nk)(1)kg(k)=k(nk)(1)kj(kj)(1)jf(j)=jf(j)k(nk)(kj)(1)k+j\displaystyle \sum_k \binom{n}{k} (-1)^k g(k) = \sum_k \binom{n}{k}(-1)^k \sum_j \binom{k}{j} (-1)^j f(j) = \sum_j f(j) \sum_k \binom{n}{k} \binom{k}{j} (-1)^{k+j}

=jf(j)k(nj)(njkj)(1)k+j=jf(j)(nj)k(1)k(njk)\displaystyle \quad = \sum_j f(j) \sum_k \binom{n}{j} \binom{n-j}{k-j} (-1)^{k+j} = \sum_{j} f(j)\binom{n}{j} \sum_k (-1)^k \binom{n-j}{k}

最后一步是做了代换,令 k=kjk = k-j

=jf(j)(nj)(11)nj\displaystyle \quad = \sum_j f(j) \binom{n}{j} (1-1)^{n-j},此时只有 nj=0n - j = 0 时,j\displaystyle \sum_j 的项 0\neq 0,此时 (11)nj=1(1-1)^{n-j} = 1

=jf(j)(nj)[n=j]=f(n)\displaystyle \quad = \sum_j f(j) \binom{n}{j} [n = j] = f(n)

重排问题

nn 个球迷抛帽子,有多少种方式 h(n,k)h(n, k) 使得恰好有 kk 个球迷得到他们自己的帽子
实际上,我们需要任选 kk 顶帽子,让其回到原来拥有者的手上,剩下的 nkn-k 顶帽子,均不回到其拥有者手上

h(n,k)=(nk)h(nk,0)=(nk)(nk)D\displaystyle h(n, k) = \binom{n}{k} h(n-k, 0) = \binom{n}{k} (n-k)_D

nDn_D 表示 nn 个物品排列时移动了每一项,这个排列就是重排

研究 nDn_D,可以发现一个递推关系

n!=kh(n,k)=k(nk)(nk)D=k(nk)kD,n0\displaystyle n! = \sum_k h(n, k) = \sum_k \binom{n}{k} (n-k)_D = \sum_k \binom{n}{k} k_D, \quad n \geqslant 0

最后一步推导同样用了 nk=kn - k = k 代换和二项式对称性

反演公式,发现 g(n)=n!,f(k)=(1)kkDg(n) = n!, \quad f(k) = (-1)^k \cdot k_D,从而 g(k)=k!, f(n)=(1)nnD\displaystyle g(k) = k!, \ f(n) = (-1)^n n_D

其解为 nD=(1)nk(nk)(1)kk!\displaystyle n_D = (-1)^n \sum_k \binom{n}{k} (-1)^k k!

考虑化简,将二项式阶乘展开

nD=0knn!(nk)!(1)n+k=n!0kn(1)kk!\displaystyle n_D = \sum_{0 \leqslant k \leqslant n} \frac{n!}{(n-k)!} (-1)^{n+k} = n! \sum_{0 \leqslant k \leqslant n} \frac{(-1)^k}{k!}

最后一步同样是做等价替换,令 knkk \leftarrow n-k

对于 nDn_D 中的和式,不难发现它就是 exx=1\text{e}^x \Big|_{x = -1} 展开,实际上 e1=k0(1)kk!\displaystyle \text{e}^{-1} = \sum_{k \geqslant 0} \frac{(-1)^k}{k!}

实际上,nD=n!eO(k)n_D = \displaystyle \frac{n!}{e} - O(k),做阶的估计需要排除的项为

O(k)=n!kn+1(1)kk!\displaystyle O(k) = n! \sum_{k \geqslant n+1} \frac{(-1)^k}{k!},令 k=kn1k' = k-n-1,之后所有的 kkk+n+1k'+n+1 代换

O(k)=n!k0(1)(k+n+1)(k+n+1)!=(1)n+1n+1k0(1)k(n+1)!(k+n+1)!\displaystyle O(k) = n! \sum_{k \geqslant 0} \frac{(-1)^{(k+n+1)}}{(k+n+1)!} = \frac{(-1)^{n+1}}{n+1} \sum_{k \geqslant 0} (-1)^k \frac{(n+1)!}{(k+n+1)!}

 =(1)n+1n+1(11n+2+1(n+2)(n+3)+)\displaystyle \quad \quad \ = \frac{(-1)^{n+1}}{n+1} \left(1 - \frac{1}{n+2} + \frac{1}{(n+2)(n+3)} + \cdots \right)

注意到 11n+2=n+1n+2\displaystyle 1 - \frac{1}{n+2} = \frac{n+1}{n+2}O(k)(1n+2,1n+1)\displaystyle O(k) \in \left(\frac{1}{n+2}, \frac{1}{n+1} \right)

但是 nDZn_D \in \mathbb{Z},所以实际上等于 n!e\displaystyle \frac{n!}{e} 四舍五入到最近的整数

nD=n!e+12+[n=0]\displaystyle n_D = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor + [n = 0]

重排问题的生成函数

n!=k(nk)(nk)D\displaystyle n! = \sum_k \binom{n}{k} (n-k)_D,两边同时除以 n!n!

1=k=0n1k!(nk)D(nk)!\displaystyle 1 = \sum_{k=0}^n \frac{1}{k!} \frac{(n-k)_D}{(n-k)!},看成是多项式卷积

[xn]1=[xn](k=0n1k!xk(nk)D(nk)!xnk)\displaystyle [x^n] 1 = [x^n] \left(\sum_{k=0}^n \frac{1}{k!}x^k \cdot \frac{(n-k)_D}{(n-k)!} x^{n-k} \right)

注意到 <10!,11!,12!,>\displaystyle \left<\frac{1}{0!}, \frac{1}{1!}, \frac{1}{2!}, \cdots \right> 对应的生成函数为 ex\text{e}^x,不妨设 D(x)=k0kDk!xkD(x) = \displaystyle \sum_{k \geqslant 0}\frac{k_D}{k!} x^k

那么可以写成卷积形式 11x=exD(x)\displaystyle \frac{1}{1-x} = e^x D(x)

最后 D(x)=11xex=11x(10!x011!x1+12!x2)D(x) = \displaystyle \frac{1}{1-x} e^{-x} = \frac{1}{1-x} \left(\frac{1}{0!}x^0 - \frac{1}{1!}x^1 + \frac{1}{2!}x^2 - \cdots \right)

根据 D(x)=k0kDk!xk\displaystyle D(x) = \sum_{k \geqslant 0} \frac{k_D}{k!} x^k,取 [xn][x^n] 的项,有

[xn]D(x)=[xn](1+x+x2+)(10!x011!x+12!x2)\displaystyle [x^n]D(x) = [x^n](1+x+x^2 + \cdots) \left(\frac{1}{0!}x^0 - \frac{1}{1!}x + \frac{1}{2!}x^2 - \cdots \right)

所以有 nDn!=k=0n(1)kk!\displaystyle \frac{n_D}{n!} = \sum_{k = 0}^{n} \frac{(-1)^k}{k!},这里是因为 11x\displaystyle \frac{1}{1-x} 展开 xjx^j 的系数总是 11

重排问题的另一种递推

首先不难发现 h(n,n2)h(n, n-2) 的值符合三角形数 {1,3,6,10,15,}\{1, 3, 6, 10, 15, \cdots \},这很好证明

h(n,n2)=(nn2)2D=(n2)\displaystyle h(n, n-2) = \binom{n}{n-2} 2_D = \binom{n}{2}

再来看 h(n,0)h(n,1)h(n, 0) - h(n, 1)

h(n,0)h(n,1)=nDn(n1)D=(n!0kn(1)kk!)(n(n1)!0kn1(1)kk!)\displaystyle h(n, 0) - h(n, 1) = n_D - n(n-1)_D = \left(n!\sum_{0 \leqslant k \leqslant n} \frac{(-1)^k}{k!} \right) - \left(n(n-1)! \sum_{0 \leqslant k \leqslant n-1} \frac{(-1)^k}{k!} \right)

 =n!(1)nn!=(1)n\displaystyle \quad \quad \ = n! \frac{(-1)^n}{n!} = (-1)^n

综上所述
nD=n(n1)D+(1)n\displaystyle n_D = n(n-1)_D + (-1)^n

特殊反演

拉格朗日反演

多项式 F(x)F(x)G(x)G(x)常数项都为 00 且一次项不为 00,并且 F(G(x))=xF(G(x)) = x,此时称 F,GF, G 互为复合逆
同时也一定有 G(F(x))=xG(F(x)) = x

[xn]F(x)=1n[x1](1G(x))n=1n[xn1](xG(x))n[x^n]F(x) = \frac{1}{n}[x^{-1}] \left(\frac{1}{G(x)} \right)^n = \frac{1}{n} [x^{n-1}] \left(\frac{x}{G(x)} \right)^n

证明如下,记 F(x)F(x)xkx^k 的项系数为 F[k]F[k],因为 F(G(x))=xF(G(x)) = x

kF[k]Gk(x)=x\displaystyle \sum_k F[k] \cdot G^k (x) = x,两边对 xx 微分

kF[k]kGk1(x)G(x)=1\displaystyle \sum_k F[k]\cdot k \cdot G^{k-1}(x) \cdot G'(x) = 1,然后两边同时除以 Gn(x)G^{n}(x)

kF[k]kGkn1(x)G(x)=1Gn(x)\displaystyle \sum_k F[k] \cdot k \cdot G^{k-n-1}(x) \cdot G'(x) = \frac{1}{G^n(x)},考虑 [x1][x^{-1}] 的项

[x1]kF[k]kGkn1(x)G(x)=[x1]1Gn(x)\displaystyle [x^{-1}]\sum_k F[k] \cdot k \cdot G^{k-n-1}(x) \cdot G'(x) = [x^{-1}]\frac{1}{G^n(x)}

对于 knk \neq n,此时 Gkn1(x)G(x)=1kn(Gkn(x))\displaystyle G^{k-n-1}(x) G'(x) = \frac{1}{k-n} \left (G^{k-n}(x) \right)'

因为 G(x)G(x) 中没有常数项并且一次项不为 00,自然 (Gkn(x)), kn\left(G^{k - n}(x) \right)', \ k \neq n 时不会有 [x1][x^{-1}] 的项,所以 [x1][x^{-1}]k=nk = n 贡献

[x1]F[n]nG1(x)G(x)=[x1]1Gn(x)\displaystyle [x^{-1}] F[n]\cdot n \cdot G^{-1}(x)G'(x) = [x^{-1}] \frac{1}{G^n (x)}

注意到 G(x)G(x)=a1+a2x+a3x2+a1x+a2x2+a3x3+\displaystyle \frac{G'(x)}{G(x)} = \frac{a_1 + a_2x + a_3x^2 + \cdots }{a_1x + a_2x^2 + a_3x^3 + \cdots }

[x1]G1(x)G(x)=1[x^{-1}] G^{-1}(x) G'(x) = 1,从而 F[n]n=[x1](1G(x))nF[n] \cdot n = [x^{-1}] \displaystyle \left(\frac{1}{G(x)} \right)^nF[n]F[n] 就是 [xn]F(x)[x^n]F(x)

从而拉格朗日反演成立

另类拉格朗日反演

对于无法求逆的整式,可以考虑用分数域,转换为常系数非 00 的整式逆
比如 (2x2+x)1(-2x^2 + x)^{-1}x=0x = 0 时不可求逆

F(x)F(x) 不可求逆,令 G(x)=F(x)xk\displaystyle G(x) = \frac{F(x)}{x^k},使得 G(x)G(x) 有常数项,那么 1F(x)=xk1G(x)\displaystyle \frac{1}{F(x)} = x^{-k} \frac{1}{G(x)}

以上面为例子,(2x2+x)1=(2x+1)1x1=x112x(-2x^2 + x)^{-1} = (-2x + 1)^{-1} x^{-1} = \displaystyle \frac{x^{-1}}{1-2x}

引理
对于常系数为 00 并且 [x1][x^1] 系数不为 00 的整式 F(x)F(x),有

[x1]F(x)Fk(x)=[k=1]\displaystyle [x^{-1}] F'(x)F^k(x) = [k = -1]

证明如下
k1k \neq -1,有 F(x)Fk(x)=(1k+1Fk+1(x))\displaystyle F'(x)F^k(x) = \left(\frac{1}{k+1}F^{k+1}(x) \right)',也是整式,没有 [x1][x^{-1}]

k=1k = -1,那么 [x1]F(x)F(x)=[x0]F(x)F(x)/x\displaystyle [x^{-1}]\frac{F'(x)}{F(x)} = [x^0] \frac{F'(x)}{F(x)/x}

注意到 F(x)/xF(x)/x 可逆,F(x)F(x)/x\displaystyle \frac{F'(x)}{F(x)/x} 的常数项实际上均为 F[1]F[1],所以右边 =1= 1,引理证毕

拉格朗日反演的一般形式

nGk[n]=k[xk]Fn(x)\displaystyle nG^k[n] = k\cdot [x^{-k}] F^{-n}(x),其中 Gk[n]G^k[n] 就是 [xn]Gk(x)[x^n] G^{k}(x)

证明如下
G(F(x))=xGk(F(x))=xk\displaystyle G(F(x)) = x \Longrightarrow G^{k}(F(x)) = x^k,两边同时对 xx 微分

((Gk)(F))F=kxk1\displaystyle \left((G^k)'(F) \right) \cdot F' = kx^{k-1},展开并注意到,GkG^{k} 中第 ii 项对应为 Gk[i]FiG^k[i] \cdot F^{i}

那么 (Gk)\displaystyle (G^k)' 对应的第 ii 项为 (iGk[i])Fi1\left(i \cdot G^k[i]\right) \cdot F^{i-1}

i0iGk[i]Fi1F=kxk1\displaystyle \sum_{i \geqslant 0} iG^k[i] \cdot F^{i-1} \cdot F' = kx^{k-1},两边同时乘上 FnF^{-n}

i0iGk[i]Fin1F=kxk1Fn\displaystyle \sum_{i \geqslant 0} iG^k[i] F^{i-n-1} F' = kx^{k-1} \cdot F^{-n},考虑 [x1][x^{-1}] 的项

[x1]i0iGk[i]Fin1F=[x1]kxk1Fn\displaystyle [x^{-1}]\sum_{i \geqslant 0} iG^k[i] F^{i-n-1} F' = [x^{-1}]kx^{k-1} \cdot F^{-n},根据引理

[x1]Fin1F=[in1=1][x^{-1}]F^{i-n-1}F' = [i-n-1 = -1],所以左边 i0iGk[i][in1=1]=[x1]kxk1Fn\displaystyle \sum_{i \geqslant 0} iG^k [i][i-n-1 = -1] = [x^{-1}] kx^{k-1} F^{-n}

等式右边,将 xk1x^{k-1} 吸收进 [x1][x^{-1}],右边多项式还必须提供 xx 的幂指为 1(k1)=k-1-(k-1) = -k,即

nGk[n]=[xk]kFn\displaystyle nG^k[n] = [x^{-k}] kF^{-n}

nGk[n]=k[xk]Fn(x)\displaystyle nG^k[n] = k\cdot [x^{-k}] F^{-n}(x)

另类拉格朗日反演
k0k \neq 0 时,根据多项式微分对应关系,[xk]F(x)=1k[xk1]F(x)\displaystyle [x^k] F(x) = \frac{1}{k} [x^{k-1}]F'(x)

那么以上拉格朗日反演的结论,可以扩展为

nGk[n]=k[xk]Fn(x)\displaystyle nG^k[n] = k[x^{-k}] F^{-n}(x)

nGk[n]=k1k[xk1](n)Fn1F\displaystyle nG^k[n] = k \cdot \frac{1}{-k} [x^{-k-1}] \cdot (-n)F^{-n-1}F'

Gk[n]=[xk1]Fn1F\displaystyle G^k[n] = [x^{-k-1}] F^{-n-1}F'

扩展拉格朗日反演

G(F(x))=xG(F(x)) = xF(x)F(x)G(x)G(x) 常数项都为 00 并且一次项不为 00HH 是另一个无要求的幂级数

[xn]H(G(x))=1n[x1]H(x)(1F(x))n\displaystyle [x^n]H(G(x)) = \frac{1}{n}[x^{-1}] H'(x)\left(\frac{1}{F(x)} \right)^n

证明如下,以下将 F(x)F(x) 简写为 FF
G(F)=x  H(G(F))=HG(F) = x \ \Longrightarrow \ H(G(F)) = H,这里令 T(x)=H(G(x))T(x) = H(G(x)),那么有
T(F)=HT(F) = H,展开后可以知道

iT[i]Fi=H\displaystyle \sum_i T[i]F^{i} = H,两边同时对 xx 微分

i0iT[i]Fi1F=H\displaystyle \sum_{i \geqslant 0} i T[i] \cdot F^{i-1}F' = H',然后两边同时乘以 FnF^{-n}

iT[i]iFin1F=HFn\displaystyle \sum_i T[i]i \cdot F^{i-n-1}F' = H' F^{-n},根据引理,取 [x1][x^{-1}] 的项

iT[i]i[in1=1]=[x1]HFn\displaystyle \sum_i T[i] i [i-n-1 = -1] = [x^{-1}] H'F^{-n},从而有

T[n]=1n[x1]HFn\displaystyle T[n] = \frac{1}{n} [x^{-1}] H'F^{-n}

有了拉格朗日反演基础,就可以处理一些广义二项级数问题了

相关练习
ZJOI2020 抽卡
EZEC-7 线段树
CF1349F2 Slime and Sequences (Hard Version)
参考解答
KrOI2021 Feux Follets 弱化版
大朋友和多叉树
参考解答
凸多边形正则划分问题
地底蔷薇

广义二项级数

广义二项级数定义如下

Bt(z)=n0(tn+1n)zntn+1\mathcal{B}_t(z) = \sum_{n \geqslant 0} \binom{tn+1}{n} \frac{z^n}{tn+1}

或者等价写成 Bt(z)=n0(tn)n1znn!\displaystyle \mathcal{B}_t(z) = \sum_{n \geqslant 0} (tn)^{\underline{n-1}} \frac{z^n}{n!}

给出几个恒等式
(1)\textbf{(1)}
Bt(z)=zBt(z)t+1\displaystyle \mathcal{B}_t(z) = z\mathcal{B}_t(z)^t + 1,或者等价写成
Bt(z)1tBt(z)t=z\displaystyle \mathcal{B}_t(z)^{1-t} - \mathcal{B}_t(z)^{-t} = z

(2)\textbf{(2)}

Bt(z)r=n0(tn+rn)rtn+rzn\displaystyle B_t(z)^r = \sum_{n \geqslant 0} \binom{tn+r}{n} \frac{r}{tn+r} z^n

(3)\textbf{(3)}

Bt(z)r1t+tBt(z)1=n0(tn+rn)zn\displaystyle \frac{\mathcal{B}_t(z)^r}{1-t+t\mathcal{B}_t(z)^{-1}} = \sum_{n \geqslant 0} \binom{tn + r}{n} z^n

证明如下,对于 (1)\textbf{(1)},令 F(z)=Bt(z)1F(z) = \mathcal{B}_t(z) - 1,那么有
F(z)=z(1+F(z))t\displaystyle F(z) = z(1+F(z))^t

此时如果令 G(z)=z(1+z)tG(z) = \displaystyle \frac{z}{(1+z)^t},那么 G(F(z))=zG(F(z)) = z,并且 G(z),F(z)G(z), F(z) 常数项为 00 并且一次项不为 00

根据拉格朗日反演,可以推知

[zn]F(z)=1n[zn1](zG(z))n=1n(ntn1)\displaystyle [z^n]F(z) = \frac{1}{n}[z^{n-1}] \left(\frac{z}{G(z)} \right)^n = \frac{1}{n} \binom{nt}{n-1}

利用吸收二项式,可以推出

1n(ntn1)=11+nt(1+ntn)\displaystyle \frac{1}{n} \binom{nt}{n-1} = \frac{1}{1+nt} \binom{1+nt}{n},于是我们得到

Bt(z)=n0(1+ntn)11+ntzn\displaystyle \mathcal{B_t}(z) = \sum_{n \geqslant 0} \binom{1+nt}{n} \frac{1}{1+nt} z^n

接下来考虑证明 (2)\textbf{(2)}

之前在证明的过程中,令 Bt=F(z)+1\mathcal{B}_t = F(z) + 1,那么这里的推广,对于 Bt(z)r=(1+F(z))r\mathcal{B}_t(z)^r = (1+F(z))^r
那么构造 H(z)=(1+z)rH(z) = (1+z)^r,这样可以对 H(F(z))H(F(z)) 用扩展拉格朗日反演

[zn]Bt(z)r=[zn]H(F(z))=1n[zn1]H(z)(zG(z))n=rn[zn1](1+z)nt+r1\displaystyle [z^n]\mathcal{B}_t(z)^r = [z^n]H(F(z)) = \frac{1}{n} [z^{n-1}]H'(z) \left(\frac{z}{G(z)} \right)^n = \frac{r}{n} [z^{n-1}](1+z)^{nt+r-1}

于是我们有
[zn]Bt(z)r=rn(nt+r1n1)\displaystyle [z^n]\mathcal{B}_t(z)^r = \frac{r}{n} \binom{nt+r-1}{n-1}

利用吸收恒等式,rn(nt+r1n1)=rnt+r(nt+rn)\displaystyle \frac{r}{n} \binom{nt+r-1}{n-1} = \frac{r}{nt+r} \binom{nt+r}{n},从而有

Bt(z)r=n0(nt+rn)rnt+rzn\displaystyle \mathcal{B}_t(z)^r = \sum_{n \geqslant 0} \binom{nt+r}{n} \frac{r}{nt+r} z^n

接下来考虑证明 (3)\textbf{(3)}
同样根据 Bt(z)=1+F(z)\displaystyle \mathcal{B}_t(z) = 1 + F(z),构造 H(z)=(1+z)r1t+t(1+z)1\displaystyle H(z) = \frac{(1+z)^r}{1-t+t(1+z)^{-1}}

这样的话,[zn]Bt(z)r1t+tBt(z)1=[zn]H(F(z))\displaystyle [z^n] \frac{\mathcal{B}_t(z)^r}{1-t+t\mathcal{B}_t(z)^{-1}} = [z^n]H(F(z))

根据拉格朗日反演
[zn]H(F(z))=1n[zn1]H(z)(zG(z))n\displaystyle [z^n]H(F(z)) = \frac{1}{n} [z^{n-1}] H'(z) \left(\frac{z}{G(z)} \right)^n

 =1n[zn1](1+z)ntr(1+z)r1(1t+t(1+z)1)+(1+z)rt(1+z)2(1t+t(1+z)1)2\displaystyle \quad \quad \ = \frac{1}{n}[z^{n-1}] (1+z)^{nt} \frac{r(1+z)^{r-1}(1-t+t(1+z)^{-1}) + (1+z)^r t(1+z)^{-2}}{(1-t+t(1+z)^{-1})^2}

 =1n[zn1](1+z)nt+r(r1(t1)z+t(1(t1)z)2)\displaystyle \quad \quad \ = \frac{1}{n}[z^{n-1}](1+z)^{nt+r} \left(\frac{r}{1-(t-1)z} + \frac{t}{(1-(t-1)z)^2} \right)

考虑将其展开,难点是第二项,实际上,第二项可以写成 (1(t1)z)2(1-(t-1)z)^{-2},用牛顿二项式展开求 ni1n-i-1
系数为 (1)ni1(2ni1)\displaystyle (-1)^{n-i-1} \binom{-2}{n-i-1},然后反转上指标

 =1ni=0n1(nt+ri)(r(t1)n1i+t(ni)(t1)n1i)\displaystyle \quad \quad \ = \frac{1}{n} \sum_{i = 0}^{n-1} \binom{nt+r}{i} \left(r(t-1)^{n-1-i} + t(n-i)(t-1)^{n-1-i} \right)

 =1n((nt+r)i=0n1(nt+ri)(t1)n1iti=0n1(nt+ri)i(t1)n1i)\displaystyle \quad \quad \ = \frac{1}{n} \left((nt+r)\sum_{i = 0}^{n-1} \binom{nt+r}{i}(t-1)^{n-1-i} - t\sum_{i = 0}^{n-1} \binom{nt+r}{i} i(t-1)^{n-1-i} \right)

对第二个求和式,应用吸收恒等式

 =1n(nt+r)(i=0n1(nt+ri)(t1)n1iti=0n1(nt+r1i1)i(t1)n1i)\displaystyle \quad \quad \ = \frac{1}{n}(nt+r) \left(\sum_{i = 0}^{n-1} \binom{nt+r}{i}(t-1)^{n-1-i} - t\sum_{i = 0}^{n-1} \binom{nt+r-1}{i-1} \cdot i(t-1)^{n-1-i} \right)

下面考虑对该式进行化简

 =1n(nt+r)[zn1]((1+z)nt+r1(t1)ztz(1+z)nt+r11(t1)z)\displaystyle \quad \quad \ = \frac{1}{n}(nt+r) [z^{n-1}] \left(\frac{(1+z)^{nt+r}}{1-(t-1)z} - \frac{tz(1+z)^{nt+r-1}}{1-(t-1)z} \right)

 =1n[zn1](nt+r)(1+z)nt+r1(1+ztz)1(t1)z=1n[zn1](nt+r)(1+z)nt+r1\displaystyle \quad \quad \ = \frac{1}{n}[z^{n-1}](nt+r) \frac{(1+z)^{nt+r-1}(1+z-tz)}{1-(t-1)z} = \frac{1}{n}[z^{n-1}] (nt+r)(1+z)^{nt+r-1}

最后得到 nt+rn(nt+r1n1)\displaystyle \frac{nt+r}{n} \binom{nt+r-1}{n-1},证毕

广义指数级数

Et(z)=n0(tn+1)n1znn!\displaystyle \mathcal{E}_t(z) = \sum_{n \geqslant 0} (tn+1)^{n-1} \frac{z^n}{n!}

同样满足以下 33 个性质

(1)\textbf{(1)}
Et(z)tlnEt(z)=z\displaystyle \mathcal{E}_t(z)^{-t} \ln \mathcal{E}_t(z) = z

(2)\textbf{(2)}
Et(z)r=n0r(tn+r)n1znn!\displaystyle \mathcal{E}_t(z)^r = \sum_{n \geqslant 0} r(tn+r)^{n-1} \frac{z^n}{n!}

(3)\textbf{(3)}
Et(z)r1ztEt(z)t=n0(tn+r)nznn!\displaystyle \frac{\mathcal{E}_t(z)^r}{1-zt\mathcal{E}_t(z)^t} = \sum_{n \geqslant 0} (tn + r)^n \frac{z^n}{n!}

证明如下
证明 (1)\textbf{(1)},实际上如果令 F(z)=lnEt(z)F(z) = \ln \mathcal{E}_t(z)Et(z)=eF(z)\mathcal{E}_t(z) = \text{e}^{F(z)}

只要证明 F(z)etF(z)=z\displaystyle \frac{F(z)}{e^{tF(z)}} = z 是否成立即可,假设它成立,只要看看能否推出 Et(z)\mathcal{E}_t(z)
求一下 Et(z)\mathcal{E}_t(z) 是多少就可以了

考虑拉格朗日反演, Et(z)=eF(z)\mathcal{E}_t(z) = e^{F(z)},令 H(z)=ezH(z) = e^zEt(z)=eF(z)=H(F(z))\mathcal{E}_t(z) = e^{F(z)} = H(F(z))

根据之前条件,如果令 G(z)=zetz\displaystyle G(z) = \frac{z}{e^{tz}},那么有 G(F(z))=zG(F(z)) = z,那么 G,FG, F 互为符合逆

用扩展拉格朗日反演

[zn]Et(z)=[zn]eF(z)=[zn]H(F(z))\displaystyle [z^n] \mathcal{E}_t(z) = [z^n] e^{F(z)} = [z^n]H(F(z))

=1n[zn1]H(z)(zG(z))n=1n[zn1]ez(etz)n=(tn+1)n1n!\displaystyle \quad \quad = \frac{1}{n} [z^{n-1}] H'(z) \left(\frac{z}{G(z)} \right)^n = \frac{1}{n}[z^{n-1}] e^z (e^{tz})^n = \frac{(tn+1)^{n-1}}{n!}

这恰好就是 Et(z)\mathcal{E}_t(z) 的定义表达式

接下来证明 (2)\textbf{(2)},实际上就是求 erF(z)e^{rF(z)}[xn][x^n] 项,那么很简单

[zn]erF(z)=1n[zn1]rerz(etz)n=r(tn+r)n1n!\displaystyle [z^n]e^{rF(z)} = \frac{1}{n} [z^{n-1}] re^{rz}(e^{tz})^n = r\frac{(tn + r)^{n-1}}{n!}

还有一种证明方法,是根据广义二项级数的极限表达式来证明

首先不难发现引理limx(xnk)xk=nkk!\displaystyle \lim_{x \to \infty} \binom{xn}{k}x^{-k} = \frac{n^k}{k!}

直接展开就可以,limx(xnk)xk=limxn(n1x)(n2x)(nnk+1x)k!\displaystyle \lim_{x \to \infty} \binom{xn}{k} x^{-k} = \lim_{x \to \infty} \frac{n(n - \frac{1}{x})(n - \frac{2}{x}) \cdots (n - \frac{n-k+1}{x})}{k!}