对于一些求总贡献的题，与许多人的常识相反，直接求期望往往比求总和更容易. 以今天联考 T1 的一个环节为例.
【例】对排列 \(P_n\)，定义 \(C(P_n):=\left|\{i:P_j>P_i,\ \forall j<i\}\right|\)，即其前缀最小值序列的不同数个数. 给定 \(n\)，求全部 \(n!\) 个排列 \(P_n\) 的 \((-1)^{C(P_n)}\) 之和.
【解】设所求答案为 \(n!E_n\)，则 \(E_n\) 是期望值. 不难写出递推式
\[E_n=-\dfrac1n\sum_{i=1}^nE_{i-1},\ \forall n\in\mathbb{N}^*, \]其含义是枚举第一个位置放 \(i\)，贡献一个因子 \((-1)\) 并覆盖后面 \(>i\) 的数，相当于只有 \(<i\) 的数有贡献.
初始条件为 \(E_0=1\)，可得 \(E_1=-1\)，恰好抵消，因此后面都是 \(E_i=0\). 这就解决了本题.
如果你不喜欢猜答案，也可以正儿八经地去解这个递推式，并不复杂.
由于 \(\dfrac1n\) 不好处理，我们把 \(n\) 乘到左边（这样同时使递推式成立的范围扩大了）：
\[nE_n=-\sum_{i=0}^{n-1}E_i,\ \forall n\in\mathbb{Z}. \]对 \(n\ge0\)，两边取差分得
\[(n+1)E_{n+1}-nE_n=-E_n,\ \forall n\in\mathbb{N}^*, \]即
\[E_{n+1}=\dfrac{n-1}{n+1}E_n,\ \forall n\in\mathbb{N}^*. \]当初值为 \(E_0=1\) 时 \(E_1=-1\)、\(E_2=0\)，后面便都是 \(0\).
当然，既然 gf 可解万物，为什么不试试呢（
对乘过 \(n\) 的递推式取 gf，两边分别化简得
\[zG'(z)=-\dfrac{z}{1-z}G(z), \]即
\[G'(z)+\dfrac1{1-z}G(z)=0. \]这是个一阶齐次线性微分方程，将其化为
\[\dfrac{G'(z)}{G(z)}=\dfrac1{z-1} \]即
\[\left(\ln G(z)\right)'=\dfrac1{z-1} \]两边积分有
\[\ln G(z)=\int\dfrac1{z-1}\mathrm{d}z. \]右边的积分等于 \(\ln(z-1)+C_0\)，所以 \(G(z)=C_1(z-1)\). 再利用 \(G(0)=E_0=1\) 得到 \(G(z)=1-z\).（这里函数取值是否有意义其实是有问题的，但并不妨碍我们求得结果.）
仅供娱乐，毕竟 OI 考场上解微分方程实在有点喜感（
另一个例子是 xcs 的远古模拟赛题，可转化为求解
\[E_n=1+\dfrac1n\sum_{i=1}^nE_{i-1}. \]与本题如出一辙.
标签：mathbb,例题,联考题,sum,nE,dfrac1,forall,一则,递推 From： https://www.cnblogs.com/abcc/p/problem1.html