跳转至

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) = \begin{cases} 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{cases} \]

實現

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

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用