跳转至

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

公式

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

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

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

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

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

考虑从 转移到 ，此时需要使欧拉数增加 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
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)))

习题

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