AIOJ

Note

The Eulerian number is meant below. Distinguish it from the Euler number and Euler's number (mathematical constants associated with Euler, such as $\gamma$ or $\mathrm{e}$ ).

In combinatorics, Eulerian numbersare the number of permutations of $1$ through $n$ with exactly $m$ elements greater than their predecessors (that is, with $m$ ascents). They are defined as follows:

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

For example, among the numbers $1$ through $3$ , there are $4$ permutations in which exactly one element is greater than its predecessor:

Permutation	Adjacent elements satisfying the 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, by the definition of $A(n, m)$ , when $n$ equals $3$ and $m$ equals $1$ , the Eulerian number is $4$ , meaning that there are $4$ permutations with $1$ element greater than its predecessor.

For small values of $n$ and $m$ , Eulerian numbers can be obtained directly:

$A(n, m)$	Permutations satisfying the 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 recursively or by dynamic programming.

First, when $m \ge n$ or $n = 0$ , no permutation satisfies the condition, so the Eulerian number is $0$ .

Second, when $m = 0$ , only the descending permutation satisfies the condition, so the Eulerian number is $1$ .

Finally, starting from a permutation of $n-1$ , insert $n$ to obtain a permutation of $n$ . Since inserting $n$ can increase the Eulerian number by at most $1$ , $A(n, m)$ can transition only from $A(n-1, m-1)$ and $A(n-1, m)$ .

Consider inserting $n$ : when $p_{i-1} < p_{i}$ , if $n$ is inserted before $p_{i}$ , that is, $n$ is inserted into an ascent, the Eulerian number is unchanged; inserting $n$ at the beginning also leaves it unchanged; otherwise, if $n$ is inserted elsewhere, the Eulerian number increases by $1$ .

For a transition from $A(n-1, m-1)$ to $A(n, m)$ , the Eulerian number must increase by $1$ . Thus, $n$ cannot be inserted inside an ascent or at the beginning, leaving $n - (m-1) - 1 = n-m$ choices.

For a transition from $A(n-1, m)$ to $A(n, m)$ , the Eulerian number must remain unchanged. Thus, $n$ can only be inserted inside an ascent or at the beginning, giving $m+1$ choices.

Combining the cases gives

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

C++

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

Python

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

Eulerian Numbers

Formula

Implementation

Exercises