Eulerian Number

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

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

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

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

公式

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

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

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

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

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

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

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

综上所述，有

实现

=== "C++"

```cpp
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"

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

习题

• CF1349F1 Slime and Sequences (Easy Version)
• CF1349F2 Slime and Sequences (Hard Version)
• UOJ 593. 新年的军队
• P7511 三到六