Eulerian Number 组合推法

· · 个人记录

我们先把满足 a_i>a_{i+1} 的位置断开 ，则其等价于将排列划分成恰好 k+1 个极长上升段的排列数，设其为 g_{k+1} 。

再设 f_k 表示将排列划分为至多 k 段的排列数，易得其为集合带标号的第二类斯特林数。

一个拥有 k 段的排列会有 n-k 个空位可以插板，插了 x 个板后会对 f_{k+x} 造成贡献，则我们有如下基本等式：

\begin{aligned} f_i=\sum_{j\leq i}{n-j\choose i-j} g_j\\ f_i=\sum_{j\leq i}{n-j\choose n-i} g_j\\ f_{n-i}=\sum_{j\geq i}{j\choose i} g_{n-j}\\ \end{aligned}

套用二项式反演：

g_{n-i}=\sum_{j\geq i} (-1)^{j-i}{j\choose i} f_{n-j}

将 f_{n-j}=\sum_{k\geq 0} (-1)^{n-j-k}{n-j\choose k}k^n 带入：

\begin{aligned} g_{n-i}=\sum_{j\geq i}(-1)^{j-i}{j\choose i}\sum_{k\geq 0} (-1)^{n-j-k}{n-j\choose k}k^n\\ g_{n-i}=\sum_{k\geq 0} (-1)^{n-i-k}k^n\sum_{j\geq i}{j\choose i}{n-j\choose k}\\ g_{n-i}=\sum_{k\geq 0} (-1)^{n-i-k}k^n\sum_{j}{j\choose i}{n-j\choose k}\\ \end{aligned}

后方的求和为上指标卷积，我们有如下结论：

\sum_k {k\choose x}{n-k\choose y}={n+1\choose x+y+1}

带入可得：

\begin{aligned} g_{n-i}=\sum_{k\geq 0} (-1)^{n-i-k}k^n{n+1\choose i+k+1}\\ g_{i}=\sum_{k\geq 0} (-1)^{i-k}k^n{n+1\choose n-i+k+1}\\ \end{aligned}

由于 g_k=\left\langle\begin{matrix}n\\k-1\end{matrix}\right\rangle ，换元后可得如下结论：

\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle=\sum_{i=0}^k (-1)^i(k+1-i)^n{n+1\choose i}