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 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).
runs, each of length 1. The number of permutation runs of the partition of 
with 
runs is sometimes denoted 
(Comtet 1974, p. 241).
contains the single run 
, while 
contains the two runs 
and 
. The following table lists the permutation runs for each
permutation 
of 
.
, 
, 
, 
, 
, 
, 
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
is an Eulerian number.
