TOPICS
Search

Permutation Run


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 n runs, each of length 1. The permutation runs in a permutation p can be computed using Runs[p] in the Wolfram Language package Combinatorica` . The number of permutation runs of the partition of {1,2,...,n} with k runs is sometimes denoted a(n,k) (Comtet 1974, p. 241).

For example, the permutation {1,2} contains the single run {1,2}, while {2,1} contains the two runs {2} and {1}. The following table lists the permutation runs for each permutation p of {1,2,3}.

ppermutation runs
{1,2,3}{1,2,3}
{1,3,2}{1,3}, {2}
{2,1,3}{2}, {1,3}
{2,3,1}{2,3}, {1}
{3,1,2}{3}, {1,2}
{3,2,1}{3}, {2}, {1}

The number a(n,k) of permutations of length n with exactly k runs is directly related to the number of permutation ascents, with k runs implying k-1 ascents (Comtet 1974, p. 241; Skiena 1990, p. 31), so

 a(n,k)=<n; k-1>,

where <n; k-1> 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

Permutation Run

Cite this as:

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

Subject classifications