A set of ascending sequences in a permutation is called a run (Graham et al. 1994) or sometimes a rise (Comtet 1974, p. 241). A sorted permutation consists of a single run, whereas a reverse permutation consists of runs, each of length 1. The permutation runs in a permutation can be computed using Runs[p] in the Wolfram Language package Combinatorica` . The number of permutation runs of the partition of with runs is sometimes denoted (Comtet 1974, p. 241).
For example, the permutation contains the single run , while contains the two runs and . The following table lists the permutation runs for each permutation of .
| permutation runs | |
| , | |
| , | |
| , | |
| , | |
| , , |
The number of permutations of length with exactly runs is directly related to the number of permutation ascents, with runs implying ascents (Comtet 1974, p. 241; Skiena 1990, p. 31), so
where is an Eulerian number.
Surprisingly, the expected length of the first run is shorter than the expected length of the second run (Gassner 1967; Skiena 1990, p. 30; Knuth 1998).
See also
Eulerian Number, Permutation, Permutation Ascent, Run
Explore with Wolfram|Alpha
References
Comtet, L. "Permutations by Number of Rises; Eulerian Numbers." §6.5 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 240-246, 1974.Gassner, B. J. "Sorting by Replacement Selection." Comm. ACM 10, 89-93, 1967.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.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Permutation Run." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PermutationRun.html