浅谈欧拉数

为什么这东西叫欧拉数呢？因为这是欧拉提出的。 ### 这玩意到底是什么？ 对于一个排列 $\pi$ 来说，我们记这个排列的升高为满足 $\pi_i<\pi_{i+1}$ 的 $i$ 的个数，形式化的说，也就是这个式子： $$\sum\limits_{i=1}^{n-1}[\pi_i<\pi_{i+1}]$$ 我们便自然想对有长度为 $n$ 且有 $k$ 个升高的排列计数。这个时候就可以定义欧拉数 $\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle$ 为长度为 $n$ 并且恰有 $k$ 个升高的排列个数。 比如说 $\{1,2,3,4\}$ 有 $11$ 个排列恰有两个上升： $$\begin{gathered}1324,1423,2314,2413,3412\\1243,1342,2341,2134,3124,4123\end{gathered}$$ 其中第一行列出了满足 $\pi_1<\pi_2>\pi_3<\pi_4$ 的排列，第二行列出了满足 $\pi_1<\pi_2<\pi_3>\pi_4$ 和 $\pi_1>\pi_2<\pi_3<\pi_4$ 的排列。所以 $\left\langle\begin{matrix}4\\2\end{matrix}\right\rangle=11$。 ### 这玩意到底怎么求？ 这部分是这篇文章的重中之重。在讲解如何求这东西之前，这里先给出一些表：  （蒯的《混凝土数学》的，主要是方便大家如果看到什么 $1\ 11\ 11\ 1$ 这样的东西就可以直接猜） 首先考虑如何 $O(n^2)$ 求，这里有一道模板题：[P2401](https://www.luogu.com.cn/problem/P2401) 一个最朴素的方法是 DP 求解。考虑将 $n$ 插入 $1,\cdots,n-1$ 的排列中，需要讨论四种情况： - 在排列的左端插入一个 $n$，这样不产生任何升高，所以这种情况从 $\left\langle\begin{matrix}n-1\\k\end{matrix}\right\rangle$ 转移来。 - 在排列的右端插入一个 $n$，这样会产生一个升高，所以这种情况由 $\left\langle\begin{matrix}n-1\\k-1\end{matrix}\right\rangle$ 转移来。 - 在某一个位置 $i$ 和 $i+1$ 中间插入 $n$，其中 $\pi_i<\pi_{i+1}$，那么这里会产生一个升高，同时会破坏原来的一个升高，所以总的升高是不变的。所以之前的排列要有 $k$ 个升高，所以，这种情况由 $k\left\langle\begin{matrix}n-1\\k\end{matrix}\right\rangle$ 转移来。 - 在某一个位置 $i$ 和 $i+1$ 中间插入 $n$，其中 $\pi_i>\pi_{i+1}$，那么这里会产生一个升高，但是不会破坏任何原有的升高，所以总而言之产生了一个升高。所以之前的排列要有 $k-1$ 个升高，所以，这种情况由 $(n-k-1)\left\langle\begin{matrix}n-1\\k-1\end{matrix}\right\rangle$转移来。 将这四种情况加起来得到第一个求欧拉数的式子： $$\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle=(k+1)\left\langle\begin{matrix}n-1\\k\end{matrix}\right\rangle+(n-k)\left\langle\begin{matrix}n-1\\k-1\end{matrix}\right\rangle$$ 这样就可以 $O(n^2)$ DP 了。 在看另一个题目之前，可以先观察几个关于欧拉数的简单恒等式。第一个是关于对称性的： $$\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle=\left\langle\begin{matrix}n\\n-k-1\end{matrix}\right\rangle$$ 这个式子很明显，考虑将长度为 $n$ 的排列反过来，原来的一个升高现在变成一个下降，原来的一个下降现在变成一个升高。如果原来的排列中有 $k$ 个升高，那么现在的排列中就会有 $n-1-k$ 个。同时因为这个排列到排列的映射显然是双射（也就是一一对应），所以这个恒等式就成立了。 接下来的几个是关于一些特殊值，这些特殊值将会给我们的一些进阶公式做铺垫： $$\left\langle\begin{matrix}n\\0\end{matrix}\right\rangle=\left\langle\begin{matrix}n\\n-1\end{matrix}\right\rangle=1,\left\langle\begin{matrix}n\\1\end{matrix}\right\rangle=\left\langle\begin{matrix}n\\n-2\end{matrix}\right\rangle=2^n-n-1$$ 首先来看左边那个。唯一满足存在 $n$ 个上升的排列为 $\{1,2,\cdots,n\}$，所以这个欧拉数为 $1$。 对于右边那个，枚举一下唯一一个放大于号位置的两边到底有多少个升高，再看看左边摆哪些数。这个时候，整个排列就确定下来了。但是因为要容斥掉左边为 $1,2,\cdots,k$ 右边为 $k+1,k+2,\cdots,n$ 的不合法排列我们有 $$\left\langle\begin{matrix}n\\n-2\end{matrix}\right\rangle=\sum\limits_{i=1}^{n-1}\binom{n}{i}-(n-1)$$ 注意到，这个东西是很显然的二项式定理，所以 $$\left\langle\begin{matrix}n\\n-2\end{matrix}\right\rangle=\sum\limits_{i=0}^{n}\binom{n}{i}-\binom{n}{0}-\binom{n}{n}-(n-1)=2^n-n-1$$ 接下来就有更炫酷的操作了： $$\left\langle\begin{matrix}n\\2\end{matrix}\right\rangle=3^n-(n+1)2^n+\binom{n+1}{2}$$ $$\left\langle\begin{matrix}n\\3\end{matrix}\right\rangle=4^n-(n+1)3^n+\binom{n+1}{2}2^n-\binom{n+1}{3}$$ 看出来什么吗？好像有一个规律呢，这就是我们的进阶公式： $$\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{k=0}^{m}\binom{n+1}{k}(m+1-k)^n(-1)^k$$ 接下来看另一道题：[LOJ 2834](https://loj.ac/problem/2834)（不瞒我说，这题能出 $n\leq 5\times 10^6$），在这个题目中，将会阐述如何证明上述公式。 考虑数学归纳法，由 $n^2$ DP 我们得到 $$\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=(m+1)\left\langle\begin{matrix}n-1\\m\end{matrix}\right\rangle+(n-m)\left\langle\begin{matrix}n-1\\m-1\end{matrix}\right\rangle$$ 考虑直接推右边，然后套进来，大概是这样子： $$(m+1)\sum\limits_{k=0}^{m}\binom{n}{k}(m+1-k)^{n-1}(-1)^k+(n-m)\sum\limits_{k=0}^{m-1}\binom{n}{k}(m-k)^{n-1}(-1)^k$$ 然后再套进来： $$\sum\limits_{k=0}^{m}\binom{n}{k}\left[(m+1)(m+1-k)^{n-1}(-1)^k+(n-m)(m-k)^{n-1}(-1)^k\right]$$ 凑一下形式： $$\sum\limits_{k=0}^{m}\binom{n}{k}\left[(m+1-k)^{n}(-1)^k+k(m+1-k)^{n-1}(-1)^k+(n-m)(m-k)^{n-1}(-1)^k\right]$$ 还是凑形式： $$\sum\limits_{k=0}^{m}\binom{n}{k}\left[(m+1-k)^{n}(-1)^k+\frac{k}{m+1-k}(m+1-k)^{n}(-1)^k+(n-m)(m-k)^{n-1}(-1)^k\right]$$ 这里有个 key observation，注意到 $\dbinom{n}{k-1}=\dfrac{k}{n+1-k}\dbinom{n}{k}$，所以可以再凑形式： $$\sum\limits_{k=0}^{m}\left(\binom{n}{k}+\binom{n}{k-1}\right)(m+1-k)^{n}(-1)^k-\sum\limits_{k=0}^{m}\binom{n}{k}\left(\frac{k}{n+1-k}-\frac{k}{m+1-k}\right)(m+1-k)^{n}(-1)^k+\sum\limits_{k=0}^{m}\binom{n}{k}(n-m)(m-k)^{n-1}(-1)^k$$ 第一个和式中的两个二项式之和很 trivial，然后后面的和式可以通分： $$\sum\limits_{k=0}^{m}\binom{n+1}{k}(m+1-k)^{n}(-1)^k-\sum\limits_{k=0}^{m}\binom{n}{k}\left(\frac{(m-n)k}{(n+1-k)(m+1-k)}\right)(m+1-k)^{n}(-1)^k+\sum\limits_{k=0}^{m}\binom{n}{k}(n-m)(m-k)^{n-1}(-1)^k$$ 然后第二个和式可以消掉一些东西： $$\sum\limits_{k=0}^{m}\binom{n+1}{k}(m+1-k)^{n}(-1)^k-\sum\limits_{k=0}^{m}(m-n)\frac{k}{(n+1-k)}\binom{n}{k}(m+1-k)^{n-1}(-1)^k+\sum\limits_{k=0}^{m}\binom{n}{k}(n-m)(m-k)^{n-1}(-1)^k$$ 对第三个和式进行代换，并且调整上下参数，第二个和式反过来用之前提到的恒等式： $$\sum\limits_{k=0}^{m}\binom{n+1}{k}(m+1-k)^{n}(-1)^k-\left(\sum\limits_{k=0}^{m}(m-n)\binom{n}{k-1}(m+1-k)^{n-1}(-1)^k+\sum\limits_{k=0}^{m}\binom{n}{k-1}(n-m)(m+1-k)^{n-1}(-1)^{k}\right)$$ 右边括号内的式子显然为 $0$，于是就有 $$\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{k=0}^{m}\binom{n+1}{k}(m+1-k)^{n}(-1)^k$$ 边界条件很简单，所以数学归纳法成立。啊，我们终于完成了这个艰巨的任务。 如果使用快速幂的话可以做到 $O(n\log n)$ 的复杂度。但是由于指数给出，同时因为幂函数是积性函数，所以可以线性筛。这个时候因为只需要对质数的取值计算幂，时间复杂度降至 $O(n)$。 Tips：在本题的官方题解中，讲述了欧拉数到值域为 $(0,1]$ 序列上的一个映射，也即如下问题： $x_1,\cdots x_n$ 为一个长度为 $n$ 的实数序列，且 $0<x_i\leq 1$。求 $k-1\leq\sum x_i<k$ 的概率。 这个的概率其实就是 $\dfrac{1}{n!}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle$，具体证明可以参见 [EI 的题解](https://www.luogu.com.cn/blog/EntropyIncreaser/solution-p5825)。 ### 这玩意能不能求一行？ 一行的话是 [P5825](https://www.luogu.com.cn/problem/P5825)。 接下来将会用两种方法求一行，顺便介绍一些有名的恒等式。 首先利用上式我们可以构造序列 $g,h$ 满足： $$g_k=\binom{n+1}{k}(-1)^k,h_k=(k+1)^n$$ 这个时候两个东西卷一卷就得了。 但是我们不主要介绍这个，反而介绍一个非常重要的恒等式，也即 Worpitzky 恒等式： $$x^n=\sum\limits_{k}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{x+k}{n}$$ 在直接证明这个东西之前，我们考虑热热身，证明如下恒等式： $$x\binom{x+k}{n}=(k+1)\binom{x+k}{n+1}+(n-k)\binom{x+k+1}{n+1}$$ 直接暴力拆二项式系数： $$\frac{x(x+k)!}{n!(x+k-n)!}=\frac{(k+1)(x+k)!}{(n+1)!(x+k-n-1)!}+\frac{(n-k)(x+k+1)!}{(n+1)!(x+k-n)!}$$ 右边两个东西凑凑形式 $$\frac{x(x+k)!}{n!(x+k-n)!}=\frac{[(k+1)(x+k-n)+(n-k)(x+k+1)](x+k)!}{(n+1)!(x+k-n)!}$$ 然后是简单的去括号： $$\frac{x(x+k)!}{n!(x+k-n)!}=\frac{(n+1)x(x+k)!}{(n+1)!(x+k-n)!}$$ 这东西显然成立。 首先从一个很容易的东西开始： $$x^{n+1}=x\cdot x^n=\sum\limits_{k=0}^{n}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle x\binom{x+k}{n}$$ 然后我们热身的东西就可以派上用场： $$x^{n+1}=\sum\limits_{k=0}^{n}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\left ((k+1)\binom{x+k}{n+1}+(n-k)\binom{x+k+1}{n+1}\right )$$ 拆括号： $$x^{n+1}=\sum\limits_{k=0}^{n}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle (k+1)\binom{x+k}{n+1}+\sum\limits_{k=0}^{n}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle(n-k)\binom{x+k+1}{n+1}$$ 看看右边，我们用之前的递推式，有 $$\sum\limits_{k=0}^{n+1}\left\langle\begin{matrix}n+1\\k\end{matrix}\right\rangle\binom{x+k}{n+1}=\sum\limits_{k=0}^{n+1}\left ((k+1)\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle+(n+1-k)\left\langle\begin{matrix}n\\k-1\end{matrix}\right\rangle\right )\binom{x+k}{n+1}$$ 注意到在 $k=n+1$ 处被求和式值为 $0$，所以适当调整一下上界，并拆括号 $$\sum\limits_{k=0}^{n+1}\left\langle\begin{matrix}n+1\\k\end{matrix}\right\rangle\binom{x+k}{n+1}=\sum\limits_{k=0}^{n}(k+1)\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{x+k}{n+1}+\sum\limits_{k=0}^{n}(n+1-k)\left\langle\begin{matrix}n\\k-1\end{matrix}\right\rangle\binom{x+k}{n+1}$$ 右边的和式简单代换一下，得到 $$\sum\limits_{k=0}^{n+1}\left\langle\begin{matrix}n+1\\k\end{matrix}\right\rangle\binom{x+k}{n+1}=\sum\limits_{k=0}^{n}(k+1)\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{x+k}{n+1}+\sum\limits_{k=-1}^{n-1}(n-k)\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{x+k+1}{n+1}$$ 然后发现这个 $k=-1$ 和 $k=n$ 时右边和式中被求和式值为 $0$，调整一下上下界即可证明该恒等式。 接下来的内容可能需要一些生成函数和有限微积分的基础知识，如果不太会的可以先跳过。 首先我们注意到 $$\Delta\left (\binom{x+k}{n}\right)=\binom{x+k}{n-1}$$ 然后做多次差分即可得到这样一个东西： $$\Delta^m\left (\binom{x+k}{n}\right)=\binom{x+k}{n-m}$$ 很好，我们可以前进一步了 $$\sum\limits_{k}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{x+k}{n-m}=\Delta^m(x^n)=\sum\limits_{j}\binom{m}{j}(-1)^{m-j}(x+j)^n$$ 我们将 $x=0$ 代入，并使用一个非常常见的公式 $$m!\left\{\begin{matrix}n\\m\end{matrix}\right\}=\sum\limits_{k}\binom{m}{k}k^n(-1)^{m-k}$$ 于是有 $$\sum\limits_{k}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{k}{n-m}=m!\left\{\begin{matrix}n\\m\end{matrix}\right\}$$ 这里有一个 key observation。我们两边对 $m$ 求和，有 $$\sum\limits_{m}\sum\limits_{k}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\binom{k}{n-m}=\sum\limits_{m}m!\left\{\begin{matrix}n\\m\end{matrix}\right\}$$ 乘上 $z^{n-m}$（换一个变量） $$\sum\limits_{k}\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle\sum\limits_{m}z^{n-m}\binom{k}{n-m}=\sum\limits_{m}z^{n-m}m!\left\{\begin{matrix}n\\m\end{matrix}\right\}$$ 发现这是个二项式定理，然后简单的代换一下最终我们得到 $$\left\langle\begin{matrix}n\\k\end{matrix}\right\rangle=\sum\limits_{k}\left\{\begin{matrix}n\\k\end{matrix}\right\}\binom{n-k}{m}(-1)^{n-k-m}k!$$ 强行拆组合数 $$\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{k}\left\{\begin{matrix}n\\k\end{matrix}\right\}\frac{(n-k)!}{m!(n-k-m)!}(-1)^{n-k-m}k!$$ 写得更加清楚一点： $$m!\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{k}\left(\left\{\begin{matrix}n\\k\end{matrix}\right\}k!(n-k)!\right)\frac{(-1)^{n-(m+k)}}{(n-(m+k))!}$$ 现在，设 $f_i=i!\left\langle\begin{matrix}n\\i\end{matrix}\right\rangle$， $g_k=\left\{\begin{matrix}n\\k\end{matrix}\right\}k!(n-k)!$， $h_k=\dfrac{(-1)^{n-k}}{(n-k)!}$，然后有 $$f_i=\sum\limits_{k}g_{k}h_{i+k}$$ 于是就很平凡了。 ### 这玩意能不能求一列？ 感觉目前没有 practical 的做法吧，就把我现在所知道的一些求法说一下。 下面的问题没有说模数的话模数默认 $998244353$。 首先来看一个问题： 给定 $m$，$q$ 次询问，每次给出一个 $n$，求 $\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle$，其中 $1\leq m\leq 20,1\leq q\leq 10^5$。 由于 $m$ 很小，我们可以用这个恒等式： $$\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{k=0}^{m}\binom{n+1}{k}(m+1-k)^{n}(-1)^k$$ 因为 $(m+1-k)$ 取值最多 $21$ 种，所以可以考虑分块打表，然后预处理阶乘即可做到 $O(qm)$ 的复杂度。 接下来是另一个恒等式：（From [P6073](https://www.luogu.com.cn/problem/P6073) Subtask 2） $$\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{k=0}^{n}k^n(-1)^{n-k-m}\binom{n+1}{k+m+1}$$ 这个恒等式与上面那个恒等式长得差不多，但是实际上是完全不一样的两个恒等式。 证明这个恒等式的过程中，一开始就出现了一个 key observation，也就是利用范德蒙德卷积拆右侧的二项式： $$\binom{n+1}{k+m+1}=\sum\limits_{j=0}^{n}\binom{j}{k}\binom{n-j}{m}$$ 如果实在记不得这个范德蒙德卷积公式的话，这里有一个生成函数的方法： 考虑在右边乘上一个 $x^n$ 并且把它拆成 $x^j$ 与 $x^{n-j}$ 的乘积，于是等式右边变成如下式子： $$\sum\limits_{j=0}^{n}x^j\binom{j}{k}x^{n-j}\binom{n-j}{m}$$ 然后你会发现我们如果设 $F(x)=\sum\limits_{i=0}^{\infty}\dbinom{i}{k}x^i$ 和 $G(x)=\sum\limits_{i=0}^{\infty}\dbinom{i}{m}x^i$，那么等式右边就是两个生成函数的乘积的 $x^n$ 的系数。 幸运的是，这两个生成函数都有简单的封闭形式，这里以 $F(x)$ 为例。（其实 $F(x)$ 和 $G(x)$ 形式是一样的，知道一个就知道另一个） 考虑到当 $i\lt k$ 的时候 $x^i$ 的系数为 $0$，所以我们可以考虑平移一下。 我们构造 $F^\prime(x)=\sum\limits_{i=0}^{\infty}\dbinom{i+k}{k}x^i$，那么可以发现 $F(x)=x^kF^\prime(x)$。 然而 $F^\prime(x)$ 的封闭形式非常简单，是 $\dfrac{1}{(1-x)^{k+1}}$。 所以，$F(x)=\dfrac{x^k}{(1-x)^{k+1}}$，同理有 $G(x)=\dfrac{x^m}{(1-x)^{m+1}}$，于是得到 $F(x)G(x)=\dfrac{x^{k+m}}{(1-x)^{k+m+2}}$。 现在我们来求它的 $x^n$ 的系数。 根据上面的推导，我们发现 $\dfrac{x^{k+m}}{(1-x)^{k+m+1}}$ 中 $x^n$ 的系数很好求，而我们发现 $$\frac{x^{k+m}}{(1-x)^{k+m+2}}=\frac{x^{k+m}}{(1-x)^{k+m+1}}\frac{1}{1-x}$$ 而这个 $\dfrac{1}{1-x}$ 相当于将系数做前缀和。所以我们的答案为 $$\sum\limits_{i=0}^{n}\binom{i}{k+m}$$ 这就是个裸的上指标求和，因此答案为 $\binom{n+1}{k+m+1}$。 于是可以直接代入 $$\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{k=0}^{n}k^n(-1)^{n-k-m}\sum\limits_{j=0}^{n}\binom{j}{k}\binom{n-j}{m}$$ 调整一下求和的上下界 $$\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{k=0}^{n}\sum\limits_{j=k}^{n}k^n(-1)^{n-k-m}\binom{j}{k}\binom{n-j}{m}$$ 交换一下求和顺序 $$\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{j=0}^{n}\sum\limits_{k=0}^{j}k^n(-1)^{n-k-m}\binom{j}{k}\binom{n-j}{m}$$ 接下来又是一个 key observation：把 $(-1)^{n-k-m}$ 拆成 $(-1)^{j-k}$ 和 $(-1)^{n-j-m}$ $$\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{j=0}^{n}\sum\limits_{k=0}^{j}k^n(-1)^{j-k}(-1)^{n-j-m}\binom{j}{k}\binom{n-j}{m}$$ 提出无关项 $$\left\langle\begin{matrix}n\\m\end{matrix}\right\rangle=\sum\limits_{j=0}^{n}(-1)^{n-j-m}\binom{n-j}{m}\sum\limits_{k=0}^{j}k^n(-1)^{j-k}\binom{j}{k}$$ 发现与 $k$ 有关的和式为斯特林数，然后这个东西与 P5828 提到的第二个恒等式等价。 当然为什么在这里写这个公式呢，因为经过大量的推导之后，我们将一列的欧拉数化成了一个类似于卷积的东西。 当然还有一种做法是平移指数基变换，这里就不做过多补充。 ### 这玩意能求对角线吗？ 注意到根据欧拉数的对称性，求对角线等价于求一列。 ### 附录 一些有关于排列相邻两数之间不等关系类问题都可以转化成欧拉数的模型，可以很好的列式子并且使用一些方法解决，具体而言可以见试看看部分。 ### 试看看！ [CF1349F1 Slime and Sequences (Easy Version)](https://www.luogu.com.cn/problem/CF1349F1) [CF1349F2 Slime and Sequences (Hard Version)](https://www.luogu.com.cn/problem/CF1349F2) [UOJ 593 新年的军队](https://uoj.ac/problem/593) [Luogu P7511 三到六](https://www.luogu.com.cn/problem/P7511)