Eulerian Number 注意 下文中的欧拉数特指 Eulerian Number。注意与 Euler numbers,Euler's number 作区分。
在计算组合中,欧拉数 (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) = \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++ Version
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 Version
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 )))
习题 build 本页面最近更新: ,更新历史 edit 发现错误?想一起完善? 在 GitHub 上编辑此页! people 本页面贡献者:OI-wiki copyright 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用