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