Permutation Ascent -- from Wolfram MathWorld

Discrete Mathematics > Combinatorics > Permutations >

Permutation Ascent

Let $p={a_1,a_2,...,a_n}$ be a permutation. Then is a permutation ascent if . For example, the permutation is composed of three ascents, namely , , and .

The number of permutations of length having ascents is given by the Eulerian number .

The total number of ascents in all permutations of order is

giving the first few terms for , 2, ... as 0, 1, 6, 36, 240, 1800, 15120, ... (Sloane's A001286).

There is an intimate connection between permutation ascents and permutation runs, with the number of ascents of length in the permutations being equal to the number of permutation runs of length (Skiena 1990, p. 31), or

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

CITE THIS AS:

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