本地源文件：docs/math__combinatorics__eulerian.md

Eulerian Number

注意

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

在计算组合中，欧拉数 （Eulerian Number）是从 11 到 𝑛n 中正好满足 𝑚m 个元素大于前一个元素（具有 𝑚m 个「上升」的排列）条件的排列个数．定义为：

𝐴(𝑛,𝑚)=⟨𝑛𝑚−1⟩A(n,m)=⟨nm−1⟩

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

排列	满足条件的相邻元素	个数
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 等于 33，𝑚m 等于 11，欧拉数值为 44，表示共有 44 个有 11 个元素大于前一个元素的排列．

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

𝐴(𝑛,𝑚)A(n,m)	满足要求的排列	个数
𝐴(1,0)A(1,0)	(1)(1)	1
𝐴(2,0)A(2,0)	(2,1)(2,1)	1
𝐴(2,1)A(2,1)	(1,2)(1,2)	1
𝐴(3,0)A(3,0)	(3,2,1)(3,2,1)	1
𝐴(3,1)A(3,1)	(1,3,2),(2,1,3),(2,3,1),(3,1,2)(1,3,2),(2,1,3),(2,3,1),(3,1,2)	4
𝐴(3,2)A(3,2)	(1,2,3)(1,2,3)	1

公式

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

首先，当 𝑚 ≥𝑛m≥n 或 𝑛 =0n=0 时，没有满足条件的排列，即此时欧拉数为 00．

其次，当 𝑚 =0m=0 时，只有降序的排列满足条件，即此时欧拉数为 11．

最后，考虑在 𝑛 −1n−1 的排列的基础上插入 𝑛n 从而得到 𝑛n 的排列，由于插入 𝑛n 至多使欧拉数增加 11，所以 𝐴(𝑛,𝑚)A(n,m) 可以仅从 𝐴(𝑛 −1,𝑚 −1)A(n−1,m−1) 处和 𝐴(𝑛 −1,𝑚)A(n−1,m) 处转移得到．

考虑 𝑛n 插入的位置：当 𝑝𝑖−1 <𝑝𝑖pi−1<pi 时，若将 𝑛n 插到 𝑝𝑖pi 之前，即将 𝑛n 插入到「上升」中，排列的欧拉数不变；此外，将 𝑛n 插在排列之前，排列的欧拉数也不变；否则，若将 𝑛n 插到其余位置，排列的欧拉数增加 11．

考虑从 𝐴(𝑛 −1,𝑚 −1)A(n−1,m−1) 转移到 𝐴(𝑛,𝑚)A(n,m)，此时需要使欧拉数增加 11，此时不能将 𝑛n 插在「上升」中或者排列开头，共有 𝑛 −(𝑚 −1) −1 =𝑛 −𝑚n−(m−1)−1=n−m 种方案．

考虑从 𝐴(𝑛 −1,𝑚)A(n−1,m) 转移到 𝐴(𝑛,𝑚)A(n,m)，此时需要欧拉数保持不变，只能将 𝑛n 插在「上升」中或者排列开头，共 𝑚 +1m+1 种方案．

综上所述，有

𝐴(𝑛,𝑚)=⎧{ {⎨{ {⎩0,𝑚>𝑛 or 𝑛=0,1,𝑚=0,(𝑛−𝑚)⋅𝐴(𝑛−1,𝑚−1)+(𝑚+1)⋅𝐴(𝑛−1,𝑚),otherwise.A(n,m)={0,m>n or n=0,1,m=0,(n−m)⋅A(n−1,m−1)+(m+1)⋅A(n−1,m),otherwise.

实现

C++Python

---|---

---|---

习题

本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！本页面贡献者：ksyx, Tiphereth-A, Enter-tainer, Great-designer, isdanni, Xeonacid, Backl1ght, CCXXXI, ChungZH, HeRaNO, iamtwz, Ir1d, Konano, Menci, mgt, shawlleyw, sshwy, StudyingFather, thredreams, XuYueming520, xyf007 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用