主題
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).

另請參閱

尤拉數, 排列, 排列遊程

使用 探索

參考文獻

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."

在 中被引用

排列上升

請引用為

Weisstein, Eric W. "Permutation Ascent." 來自 —— 資源。 https://mathworld.tw/PermutationAscent.html

主題分類