主题
Search

排列上升

下载 Mathematica 笔记本下载 Wolfram 笔记本

设 p={a_1,a_2,...,a_n} 为一个排列。那么 i 是一个排列上升，如果 a_i<a_(i+1)。例如，排列 {1,2,3,4} 由三个上升组成，即 {1,2}、 {2,3} 和 {3,4}。

长度为 n 的排列中，具有 k 个上升的排列的数量由欧拉数 <n; k> 给出。

阶数为 n 的所有排列中，上升的总数为

a_n=1/2(n-1)n!,

对于 n=1, 2, ...，给出前几项为 0, 1, 6, 36, 240, 1800, 15120, ... (OEIS A001286)。

排列上升和排列游程之间存在密切联系，其中排列 {1,2,...,n} 中长度为 k 的上升数等于长度为 k^'=k+1 的排列游程 a(n,k^') 的数量 (Skiena 1990, p. 31)，或者

<n; k>=a(n,k+1).

另请参阅

欧拉数, 排列, 排列游程

使用 Wolfram|Alpha 探索

参考文献

Bona, M. Combinatorics of Permutations. Boca Raton, FL: Chapman & Hall/CRC, 2004.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, 1998.Mannila, H. "Measures of Presortedness and Optimal Sorting Algorithms." IEE Trans. Comput. 34, 318-325, 1985.Skiena, S. "Runs and Eulerian Numbers." §1.3.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 30-31, 1990.Sloane, N. J. A. Sequence A001286/M4225 in "The On-Line Encyclopedia of Integer Sequences."

在 Wolfram|Alpha 中被引用

排列上升

请引用为

Weisstein, Eric W. "Permutation Ascent." 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/PermutationAscent.html

主题分类