Asusetic
0%

记一道数学题

发表于 分类于 Valine：
本文字数： 4.2k 阅读时长 ≈ 4 分钟

来自FJOI D2T3

记一道数学题

$\mathrm{D} 为微分算子，即为微分算子，即\mathrm{D}=\dfrac{\mathrm{d}}{\mathrm{d}x}$

Update : 更新更简洁的生成函数做法

为了式子的简洁忽略掉了一些 corner case

省略的求和指标一般是对 ii 求和

（颓了节美术课就搞出来了，考的时候在干嘛淦）

题

设 an=nan−1+n(n−1)an−22+(−1)n(1−n2)a_n=\dfrac{na_{n-1}+n(n-1)a_{n-2}}{2}+(-1)^n(1-\dfrac{n}{2})

求 ∑(ni)(n−i+1)ai\sum\binom{n}{i}(n-i+1)a_i

OI版

看到类似 ni−1‾an−in^{\underline{i-1}}a_{n-i} 的可以考虑除个 n!n! 搞 EGF

设 bn=ann!b_n=\dfrac{a_n}{n!}

则 2bn=bn−1+bn−2+2×(−1)nn!−n(−1)nn!2b_n=b_{n-1}+b_{n-2}+\dfrac{2\times(-1)^n}{n!}-\dfrac{n(-1)^n}{n!}

设 bnb_n 的生成函数是 B(x)B(x)

n(−1)nn(-1)^n 的 EGF 就是 xDe−x=−xe−xx\mathrm{D} e^{-x}=-xe^{-x}

则 2B(x)=xB(x)+x2B(x)+2e−x+xe−x2B(x)=xB(x)+x^2B(x)+2e^{-x}+xe^{-x}

解出来 B(x)=(x+2)e−x2−x−x2=e−x1−xB(x)=\dfrac{(x+2)e^{-x}}{2-x-x^2}=\dfrac{e^{-x}}{1-x}

设 sn=∑(ni)(n−i+1)ai=∑(ni)(n−i)ai+∑(ni)ais_n=\sum\binom{n}{i}(n-i+1)a_i=\sum\binom{n}{i}(n-i)a_i+\sum\binom{n}{i}a_i

考虑前一项是 {i}\{i\} 与 {ai}\{a_i\} 的二项卷积，即 xDexe−x1−x=x1−xx\mathrm{D} e^{x}\dfrac{e^{-x}}{1-x}=\dfrac{x}{1-x}

后一项是 {1}\{1\} 与 {ai}\{a_i\} 的二项卷积，即exe−x1−x=11−xe^x\dfrac{e^{-x}}{1-x}=\dfrac{1}{1-x}

则 sns_n 的 EGF 为 1+x1−x\dfrac{1+x}{1-x}

sn=n![xn]1+x1−x=n![xn][(1+x)(1+x+x2)+… ]=2n!s_n=n![x^n]\dfrac{1+x}{1-x}=n![x^n][(1+x)(1+x+x^2)+\dots]=2n!

MO版

看到这个 nan−1n(n−1)an−2na_{n-1} \quad n(n-1)a_{n-2} 就先除个 n!n! ，设 bn=ann!b_n=\dfrac{a_n}{n!}

2bn=bn−1+bn−2+2×(−1)nn!+(−1)n−1(n−1)!2b_n=b_{n-1}+b_{n-2}+\dfrac{2\times(-1)^n}{n!}+\dfrac{(-1)^{n-1}}{(n-1)!}

2bn−1=bn−2+bn−3+2×(−1)n−1(n−1)!+(−1)n−2(n−2)!2b_{n-1}=b_{n-2}+b_{n-3}+\dfrac{2\times(-1)^{n-1}}{(n-1)!}+\dfrac{(-1)^{n-2}}{(n-2)!}

加起来

2bn+bn−1=2bn−2+bn−3+2×(−1)nn!+(−1)n−1(n−1)!+2×(−1)n−1(n−1)!+(−1)n−2(n−2)!2b_n+b_{n-1}=2b_{n-2}+b_{n-3}+\dfrac{2\times(-1)^n}{n!}+\dfrac{(-1)^{n-1}}{(n-1)!}+\dfrac{2\times(-1)^{n-1}}{(n-1)!}+\dfrac{(-1)^{n-2}}{(n-2)!}

继续拆开

2bn+bn−1=3×(−1)nn!+3×(−1)n−1(n−1)!+3×(−1)n−2(n−2)!+⋯+2×(−1)22!+(−1)11!+2b2+b12b_n+b_{n-1}=\dfrac{3\times(-1)^n}{n!}+\dfrac{3\times(-1)^{n-1}}{(n-1)!}+\dfrac{3\times(-1)^{n-2}}{(n-2)!}+\dots+\dfrac{2\times(-1)^{2}}{2!}+\dfrac{(-1)^1}{1!}+2b_2+b_1

设 cn=bn−∑i(−1)ii!c_n=b_n-\sum\limits_i\dfrac{(-1)^i}{i!}

对比上面的式子能发现 2cn+cn−1=02c_n+c_{n-1}=0 且 c1=0c_1=0

所以所有 cn=0c_n=0 即 bn=∑i(−1)ii!b_n=\sum\limits_i\dfrac{(-1)^i}{i!}

(ni)ai=ni‾bi=ni‾∑j(−1)jj!\binom{n}{i}a_i=n^{\underline{i}}b_i=n^{\underline{i}}\sum\limits_j\dfrac{(-1)^j}{j!}

原式为 ∑(n−i+1)ni‾∑j(−1)jj!=∑(ni+1‾+ni‾)∑j(−1)jj!\sum(n-i+1)n^{\underline{i}}\sum\limits_j \dfrac{(-1)^j}{j!}=\sum (n^{\underline{i+1}}+n^{\underline{i}})\sum\limits_j \dfrac{(-1)^j}{j!}

考虑 ni‾=Dixn∣x=1n^{\underline{i}}=\mathrm{D}^i x^n\big|_{x=1}

则 ∑(ni+1‾+ni‾)∑j(−1)jj!=(∑(1+D)Di∑j(−1)jj!xn)∣x=1\sum (n^{\underline{i+1}}+n^{\underline{i}})\sum\limits_j \dfrac{(-1)^j}{j!}=(\sum(1+\mathrm{D})\mathrm{D}^i\sum\limits_j\dfrac{(-1)^j}{j!}x^n)\Big|_{x=1}

=((1+D)∑Di∑j(−1)jj!)xn∣x=1=((1+\mathrm{D})\sum\mathrm{D}^i\sum\limits_{j}\dfrac{(-1)^j}{j!})x^n\Big|_{x=1}

交换求和 省略 ∣x=1\big|_{x=1}

(1+D)∑j(−1)jj!∑i≥jDixn=(1+D)∑j(−1)jj!Dj1−Dxn(1+\mathrm{D})\sum\limits_{j} \dfrac{(-1)^j}{j!}\sum\limits_{i \ge j} \mathrm{D}^ix^n=(1+\mathrm{D})\sum\limits_j \dfrac{(-1)^j}{j!}\dfrac{\mathrm{D}^j}{1-\mathrm{D}}x^n （没错就是可以把微分算子当作一个字母处理）

干掉求和号

1+D1−De−Dxn\dfrac{1+\mathrm{D}}{1-\mathrm{D}}e^{-\mathrm{D}} x^n

1+D1−D(x−1)n=1+D1−Dxn∣x=0=2n!\dfrac{1+\mathrm{D}}{1-\mathrm{D}}(x-1)^n=\dfrac{1+\mathrm{D}}{1-\mathrm{D}}x^n\big|_{x=0}=2n! （就是对 D\mathrm{D} 展开了幂级数）

所以原式 =2n!=2n!

Asusetic eru quionours