Eulerian Number

注意

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

在计算组合中,欧拉数(Eulerian Number)是从 中正好满足 个元素大于前一个元素(具有 个“上升”的排列)条件的排列 个数。定义为:

例如,从数字 一共有 种排列使得恰好有一个元素比前面的数字大:

排列满足要求的排列个数
1 2 31, 2 & 2, 32
1 3 21, 31
2 1 31, 31
2 3 12, 31
3 1 21, 21
3 2 10

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

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

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

公式

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

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

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

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

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

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

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

综上所述,有

实现

1
2
3
4
5
6
7
// C++ Version
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
# Python Version
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)))

习题


评论