linguistic:voice_change
Ascents, descents, runs, exceedances, records

An ascent of a permutation σ of n is any position i < n where the following value is bigger than the current one. That is, i is an ascent if σ (i) < σ (i + 1) {\displaystyle \sigma (i)<\sigma (i{+}1)}. For example, the permutation 3452167 has ascents (at positions) 1, 2, 5, and 6.

Similarly, a descent is a position i < n with σ (i) > σ (i + 1) {\displaystyle \sigma (i)>\sigma (i{+}1)}, so every i with 1 ≤ i < n {\displaystyle 1\leq i<n} is either an ascent or a descent.

An ascending run of a permutation is a nonempty increasing contiguous subsequence that cannot be extended at either end; it corresponds to a maximal sequence of successive ascents (the latter may be empty: between two successive descents there is still an ascending run of length 1). By contrast an increasing subsequence of a permutation is not necessarily contiguous: it is an increasing sequence obtained by omitting some of the values of the one-line notation.For example, the permutation 2453167 has the ascending runs 245, 3, and 167, while it has an increasing subsequence 2367.

If a permutation has k − 1 descents, then it must be the union of k ascending runs.

The number of permutations of n with k ascents is (by definition) the Eulerian number ⟨ n k ⟩ {\displaystyle \textstyle \left\langle {n \atop k}\right\rangle }; this is also the number of permutations of n with k descents. Some authors however define the Eulerian number ⟨ n k ⟩ {\displaystyle \textstyle \left\langle {n \atop k}\right\rangle } as the number of permutations with k ascending runs, which corresponds to k − 1 descents.

An exceedance of a permutation σ σ... σ is an index j such that σ > j. If the inequality is not strict (that is, σ ≥ j), then j is called a weak exceedance. The number of n -permutations with k exceedances coincides with the number of n -permutations with k descents.

A record or left-to-right maximum of a permutation σ is an element i such that σ (j) < σ (i) for all j < i.