Skip to content

Eulerian Number

Note

The Eulerian number discussed below specifically refers to the Eulerian number. Distinguish it from Euler number, and Euler's number (referring to mathematical constants related to Euler such as \(\gamma\) or \(\mathrm{e}\)).

In combinatorics, the Eulerian Number is the number of permutations of \(1\) to \(n\) in which exactly \(m\) elements are greater than the previous element (permutations with \(m\) "ascents"). It is defined as:

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

For example, there are \(4\) permutations from the numbers \(1\) to \(3\) where exactly one element is greater than the previous element:

Permutation Adjacent elements satisfying condition Count
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

Thus, according to the definition of \(A(n, m)\): if \(n = 3\) and \(m = 1\), the Eulerian number is \(4\), indicating there are \(4\) permutations with exactly \(1\) element greater than the previous element.

For small values of \(n\) and \(m\), the Eulerian numbers can be directly obtained:

\(A(n, m)\) Permutations satisfying condition Count
\(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

Formula

Eulerian numbers can be computed using recurrence or recursive methods.

First, when \(m \ge n\) or \(n = 0\), there are no permutations satisfying the condition, i.e., the Eulerian number is \(0\).

Second, when \(m = 0\), only descending permutations satisfy the condition, i.e., the Eulerian number is \(1\).

Finally, consider inserting \(n\) into a permutation of \(n-1\) to obtain a permutation of \(n\). Since inserting \(n\) can increase the Eulerian number by at most \(1\), \(A(n, m)\) can be derived only from \(A(n-1, m-1)\) and \(A(n-1, m)\).

Consider the insertion position of \(n\): when \(p_{i-1} < p_{i}\), if \(n\) is inserted before \(p_{i}\), i.e., into an "ascent", the Eulerian number of the permutation remains unchanged; additionally, inserting \(n\) at the beginning of the permutation also leaves the Eulerian number unchanged. Otherwise, if \(n\) is inserted elsewhere, the Eulerian number increases by \(1\).

Consider transitioning from \(A(n-1, m-1)\) to \(A(n, m)\). Here, the Eulerian number must increase by \(1\), so \(n\) cannot be inserted into an "ascent" or at the beginning of the permutation. There are \(n - (m-1) - 1 = n-m\) such positions.

Consider transitioning from \(A(n-1, m)\) to \(A(n, m)\). Here, the Eulerian number must remain unchanged, so \(n\) can only be inserted into an "ascent" or at the beginning of the permutation, giving \(m+1\) possible positions.

In summary,

\[ 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} \]

Implementation

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

Exercises

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