线性求欧拉数单项

设在 $1\sim n$ 的排列中钦定 $k$ 个位置为上升的方案数为 $f\left(n,k\right)$
那么，$\displaystyle f\left(n,k\right)=\sum_{m}\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle\times\binom{m}{k}$.
根据二项式反演，有 $\displaystyle \left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum_{k}f\left(n,k\right)\binom{k}{m}\left(-1\right)^{k-m}$.
单个上升段的 EGF 为 $e^x-1$，则钦定 $k$ 个位置上升，有 $n-k$ 个上升段的生成函数 $\left(e^x-1\right)^{n-k}$

展开可得

$$ \begin{aligned} \left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=&\sum_{k}f\left(n,k\right)\binom{k}{m}\left(-1\right)^{k-m}\\ =&\sum_{k}\left[x^n/n!\right]\left(e^x-1\right)^{n-k}\binom{k}{m}\left(-1\right)^{k-m}\\ =&\sum_{k}\sum_{i}\binom{n-k}{i}i^{n}\left(-1\right)^{n-k-i}\binom{k}{m}\left(-1\right)^{k-m}\\ =&\left(-1\right)^{n+m}\sum_{i}\left(-1\right)^ii^n\sum_{k}\binom{n-k}{i}\binom{k}{m}\\ =&\left(-1\right)^{n+m}\sum_{i}\left(-1\right)^ii^n\binom{n+1}{i+m+1} \end{aligned} $$

而众所周知，欧拉数具有对称性，$\displaystyle \left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\left\langle\begin{matrix}n\\n-m-1\end{matrix}\right\rangle$，把 $m^{\prime}=n-m-1$ 带入可得

$$ \left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\left(-1\right)^{m+1}\sum_{i}\left(-1\right)^{i}i^n\binom{n+1}{n-m+i} $$

具体数学 6.67

证明:

$$\sum_{k}\left\{\begin{matrix}n+1\\k+1\end{matrix}\right\}\binom{n-k}{m-k}\left(-1\right)^{m-k}k!=\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle$$

代数证明

左边展开可得

$$ \begin{aligned} &\sum_{k}\left\{\begin{matrix}n+1\\k+1\end{matrix}\right\}\binom{n-k}{m-k}\left(-1\right)^{m-k}k!\\ =&\sum_{k}\dfrac{k!}{\left(k+1\right)!}\binom{n-k}{m-k}\left(-1\right)^{m+k}\sum_{i}\binom{k+1}{i}\left(-1\right)^{k+1-i}i^{n+1}\\ =&\sum_{i}i^{n+1}\left(-1\right)^{m+i+1}\sum_{k}\dfrac{1}{k+1}\binom{k+1}{i}\binom{n-k}{n-m}\\ =&\sum_{i}i^{n+1}\left(-1\right)^{m+i+1}\sum_{k}\dfrac{1}{i}\binom{k}{i-1}\binom{n-k}{n-m}\\ =&\sum_{i}i^{n}\left(-1\right)^{m+i+1}\binom{n+1}{n-m+i} \end{aligned} $$

组合证明

左右的组合意义均为，有一个 $n+1$ 的排列，要求恰好有 $m$ 个上升，且 $p_1=n+1$ 的方案数。

右边显然。

左边: 首先容斥，考虑钦定了 $m-k$ 个位置为下降，容斥系数为 $\left(-1\right)^{m-k}$。此时有 $k+1$ 个下降段，且 $n+1$ 所在的那个下降段必须在第一个位置，因此方案数为 $\displaystyle \begin{Bmatrix}n+1\\k+1\end{Bmatrix}\times k!$。还需要在剩下 $n-k$ 个位置里找出钦定的那些下降位，方案数 $\displaystyle \binom{n-k}{m-k}$，因此总的方案数即为:

$$\sum_{k}\left\{\begin{matrix}n+1\\k+1\end{matrix}\right\}\binom{n-k}{m-k}\left(-1\right)^{m-k}k!$$