跳转至

Eulerian Number

注意

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

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

\[ A(n, m) = \left\langle \begin{matrix} n\\ m - 1 \end{matrix} \right\rangle \]

例如，从数字 \(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) = \left\{ \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} \right. \]

实现

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

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

习题