Eulerian Number

注意

下文中的欧拉数特指 Eulerian number。注意与 Euler number，以及 Euler’s number（指与欧拉相关的数学常数例如 $\gamma$ 或 $\mathrm{e}$）作区分。

在计算组合中，欧拉数（Eulerian Number）是从 $1$ 到 $n$ 中正好满足 $m$ 个元素大于前一个元素（具有 $m$ 个「上升」的排列）条件的排列 个数。定义为：

$$A(n,m)=⟨\begin{array}{c}n\\ m-1\end{array}⟩$$

例如，从数字 $1$ 到 $3$ 一共有 $4$ 种排列使得恰好有一个元素比前一个元素大：

排列	满足条件的相邻元素	个数
1 2 3	1, 2 & 2, 3	2
1 3 2	1, 3	1
2 1 3	1, 3	1
2 3 1	2, 3	1
3 1 2	1, 2	1
3 2 1		0

所以按照 $A(n,m)$ 定义：如果 $n$ 等于 $3$，$m$ 等于 $1$，欧拉数值为 $4$，表示共有 $4$ 个有 $1$ 个元素大于前一个元素的排列。

对于 $n$ 和 $m$ 值比较小的欧拉数来说，我们可以直接得到结果：

$A(n,m)$	满足要求的排列	个数
$A(1,0)$	$(1)$	1
$A(2,0)$	$(2,1)$	1
$A(2,1)$	$(1,2)$	1
$A(3,0)$	$(3,2,1)$	1
$A(3,1)$	$(1,3,2),(2,1,3),(2,3,1),(3,1,2)$	4
$A(3,2)$	$(1,2,3)$	1

公式

可以通过递推或者递归的方法计算欧拉数。

首先，当 $m\ge n$ 或 $n=0$ 时，没有满足条件的排列，即此时欧拉数为 $0$。

其次，当 $m=0$ 时，只有降序的排列满足条件，即此时欧拉数为 $1$。

最后，考虑在 $n-1$ 的排列的基础上插入 $n$ 从而得到 $n$ 的排列，由于插入 $n$ 至多使欧拉数增加 $1$，所以 $A(n,m)$ 可以仅从 $A(n-1,m-1)$ 处和 $A(n-1,m)$ 处转移得到。

考虑 $n$ 插入的位置：当 $p_{i-1}<p_i$ 时，若将 $n$ 插到 $p_i$ 之前，即将 $n$ 插入到「上升」中，排列的欧拉数不变；此外，将 $n$ 插在排列之前，排列的欧拉数也不变；否则，若将 $n$ 插到其余位置，排列的欧拉数增加 $1$。

考虑从 $A(n-1,m-1)$ 转移到 $A(n,m)$，此时需要使欧拉数增加 $1$，此时不能将 $n$ 插在「上升」中或者排列开头，共有 $n-(m-1)-1=n-m$ 种方案。

考虑从 $A(n-1,m)$ 转移到 $A(n,m)$，此时需要欧拉数保持不变，只能将 $n$ 插在「上升」中或者排列开头，共 $m+1$ 种方案。

综上所述，有

$$A(n,m)=\{\begin{array}{ll}0,& m>n\text{ or }n=0,\\ 1,& m=0,\\ (n-m)\cdot A(n-1,m-1)+(m+1)\cdot A(n-1,m),& \text{otherwise}.\end{array}$$

实现

[list2tab]

• C++

  int eulerianNumber(int n, int m) {
    if (m >= n || n == 0) return 0;
    if (m == 0) return 1;
    return (((n - m) * eulerianNumber(n - 1, m - 1)) +
            ((m + 1) * eulerianNumber(n - 1, m)));
  }

• Python

  def eulerianNumber(n, m):
      if m >= n or n == 0:
          return 0
      if m == 0:
          return 1
      return ((n - m) * eulerianNumber(n - 1, m - 1)) + (
          (m + 1) * eulerianNumber(n - 1, m)
      )

习题

• CF1349F1 Slime and Sequences (Easy Version)
• CF1349F2 Slime and Sequences (Hard Version)
• UOJ 593. 新年的军队
• P7511 三到六