Permutations - Permutations in Combinatorics - Ascents, Descents and Runs

Ascents, Descents and Runs

An ascent of a permutation σ of n is any position i < n where the following value is bigger than the current one. That is, if σ = σ1σ2...σn, then i is an ascent if σi < σi+1.

For example, the permutation 3452167 has ascents (at positions) 1,2,5,6.

Similarly, a descent is a position i < n with σi > σi+1, so every i with either is an ascent or is a descent of σ.

The number of permutations of n with k ascents is the Eulerian number ; this is also the number of permutations of n with k descents.

An ascending run of a permutation is a nonempty increasing contiguous subsequence of the permutation 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 of elements obtained from the permutation by omitting the values at some positions. 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. Hence, the number of permutations of n with k ascending runs is the same as the number of permutations with k − 1 descents.

Read more about this topic:  Permutations, Permutations in Combinatorics

Famous quotes containing the word runs:

    In football they measure forty-yard sprints. Nobody runs forty yards in basketball. Maybe you run the ninety-four feet of the court; then you stop, not on a dime, but on Miss Liberty’s torch. In football you run over somebody’s face.
    Donald Hall (b. 1928)