跳转至

# Eulerian Number

注意

下文中的欧拉数特指 Eulerian number．注意与 Euler number，以及 Euler's number（指与欧拉相关的数学常数例如 𝛾 γ 或 e e）作区分．

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

𝐴(𝑛,𝑚)=⟨𝑛 𝑚−1⟩A(n,m)=⟨n m−1⟩

例如，从数字 1 1 到 3 3 一共有 4 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 3，𝑚 m 等于 1 1，欧拉数值为 4 4，表示共有 4 4 个有 1 1 个元素大于前一个元素的排列．

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

𝐴(𝑛,𝑚)A(n,m) | 满足要求的排列 | 个数
--- | --- | ---
𝐴(1,0)A(1,0) | (1)(1) | 1
𝐴(2,0)A(2,0) | (2,1)(2,1) | 1
𝐴(2,1)A(2,1) | (1,2)(1,2) | 1
𝐴(3,0)A(3,0) | (3,2,1)(3,2,1) | 1
𝐴(3,1)A(3,1) | (1,3,2),(2,1,3),(2,3,1),(3,1,2)(1,3,2),(2,1,3),(2,3,1),(3,1,2) | 4
𝐴(3,2)A(3,2) | (1,2,3)(1,2,3) | 1

## 公式

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

首先，当 𝑚 ≥𝑛 m≥n 或 𝑛 =0 n=0 时，没有满足条件的排列，即此时欧拉数为 0 0．

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

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

考虑 𝑛 n 插入的位置：当 𝑝 𝑖−1 <𝑝 𝑖 p i−1<p i 时，若将 𝑛 n 插到 𝑝 𝑖 p i 之前，即将 𝑛 n 插入到「上升」中，排列的欧拉数不变；此外，将 𝑛 n 插在排列之前，排列的欧拉数也不变；否则，若将 𝑛 n 插到其余位置，排列的欧拉数增加 1 1．

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

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

综上所述，有

𝐴(𝑛,𝑚)=⎧{ {⎨{ {⎩0,𝑚>𝑛 o r 𝑛=0,1,𝑚=0,(𝑛−𝑚)⋅𝐴(𝑛−1,𝑚−1)+(𝑚+1)⋅𝐴(𝑛−1,𝑚),o t h e r w i s e.A(n,m)={0,m>n or n=0,1,m=0,(n−m)⋅A(n−1,m−1)+(m+1)⋅A(n−1,m),otherwise.

## 实现

C++Python

    1
    2
    3
    4
    5
    6
    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)));
    }

    1
    2
    3
    4
    5
    6
    7
    8
    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 三到六

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：ksyx, Tiphereth-A, Enter-tainer, Great-designer, isdanni, Xeonacid, Backl1ght, CCXXXI, ChungZH, HeRaNO, iamtwz, Ir1d, Konano, Menci, mgt, shawlleyw, sshwy, StudyingFather, thredreams, XuYueming520, xyf007
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用