TOPICS
Search

Permutation Ascent

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

Let p={a_1,a_2,...,a_n} be a permutation. Then i is a permutation ascent if a_i<a_(i+1). For example, the permutation {1,2,3,4} is composed of three ascents, namely {1,2}, {2,3}, and {3,4}.

The number of permutations of length n having k ascents is given by the Eulerian number <n; k>.

The total number of ascents in all permutations of order n is

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

giving the first few terms for n=1, 2, ... as 0, 1, 6, 36, 240, 1800, 15120, ... (OEIS A001286).

There is an intimate connection between permutation ascents and permutation runs, with the number of ascents of length k in the permutations {1,2,...,n} being equal to the number of permutation runs a(n,k^') of length k^'=k+1 (Skiena 1990, p. 31), or

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

See also

Eulerian Number, Permutation, Permutation Run

Explore with Wolfram|Alpha

References

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

Referenced on Wolfram|Alpha

Permutation Ascent

Cite this as:

Weisstein, Eric W. "Permutation Ascent." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PermutationAscent.html

Subject classifications