Eulerian Number

注意

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

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

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

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

排列	满足要求的排列	个数
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

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

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

	满足要求的排列	个数
		1
		1
		1
		1
		4
		1

公式

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

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

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

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

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

考虑从转移到，此时需要使欧拉数增加 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.

实现

C++Python

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

习题

本页面最近更新：2022/12/13 11:14:54，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：ChungZH, Great-designer, iamtwz, Ir1d, isdanni, ksyx, Menci, xyf007
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用