跳转至

Eulerian Number

注意

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

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

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

排列 满足条件的相邻元素 个数
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

所以按照 定义：如果 等于 ， 等于 ，欧拉数值为 ，表示共有 个有 个元素大于前一个元素的排列。

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

满足要求的排列 个数
1
1
1
1
4
1

公式

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

首先，当 或 时，没有满足条件的排列，即此时欧拉数为 。

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

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

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

考虑从 转移到 ，此时需要使欧拉数增加 ，此时不能将 插在「上升」中或者排列开头，共有 种方案。

考虑从 转移到 ，此时需要欧拉数保持不变，只能将 插在「上升」中或者排列开头，共 种方案。

综上所述，有

实现

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)
    )

习题

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