Eulerian Number
注意
下文中的欧拉数特指 Eulerian Number。注意与 Euler numbers,Euler's number 作区分。
在计算组合中,欧拉数(Eulerian Number)是从 1 到 n 中正好满足 m 个元素大于前一个元素(具有 m 个“上升”的排列)条件的排列 个数。定义为:
例如,从数字 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 种方案。
综上所述,有
实现¶
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 |
|
习题¶
- CF1349F1 Slime and Sequences (Easy Version)
- CF1349F2 Slime and Sequences (Hard Version)
- UOJ 593. 新年的军队
- P7511 三到六
build本页面最近更新:,更新历史
edit发现错误?想一起完善? 在 GitHub 上编辑此页!
people本页面贡献者:OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用