sym-0.9: Permutations, patterns, and statistics

Maintainer Anders Claesson None

Math.Perm.Stat

Description

Common permutation statistics. To avoid name clashes this module is best imported `qualified`; e.g.

``` import qualified Math.Perm.Stat as S
```

Synopsis

# Documentation

asc :: Perm -> IntSource

The number of ascents. An ascent in `w` is an index `i` such that `w[i] < w[i+1]`.

des :: Perm -> IntSource

The number of descents. A descent in `w` is an index `i` such that `w[i] > w[i+1]`.

exc :: Perm -> IntSource

The number of excedances: positions `i` such that `w[i] > i`.

fp :: Perm -> IntSource

The number of fixed points: positions `i` such that `w[i] == i`.

sfp :: Perm -> IntSource

The number of strong fixed points (also called splitters): positions `i` such that `w[j] < i` for `j < i` and `w[j] > i` for `j > i`.

cyc :: Perm -> IntSource

The number of cycles: orbits of the permutation when viewed as a function.

inv :: Perm -> IntSource

The number of inversions: pairs `(i,j)` such that `i < j` and `w[i] > w[j]`.

maj :: Perm -> IntSource

The major index is the sum of descents.

The co-major index is the sum of descents.

The number of peaks: positions `i` such that `w[i-1] < w[i]` and `w[i] > w[i+1]`.

The number of valleys: positions `i` such that `w[i-1] > w[i]` and `w[i] < w[i+1]`.

The number of double ascents: positions `i` such that `w[i-1] < w[i] < w[i+1]`.

The number of double descents: positions `i` such that `w[i-1] > w[i] > w[i+1]`.

The number of left-to-right minima: positions `i` such that `w[i] < w[j]` for all `j < i`.

The number of left-to-right maxima: positions `i` such that `w[i] > w[j]` for all `j < i`.

The number of right-to-left minima: positions `i` such that `w[i] < w[j]` for all `j > i`.

The number of right-to-left maxima: positions `i` such that `w[i] > w[j]` for all `j > i`.

The first (left-most) element in the standardization. E.g., `head "231" = head (fromList [1,2,0]) = 1`.

The last (right-most) element in the standardization. E.g., `last "231" = last (fromList [1,2,0]) = 0`.

lir :: Perm -> IntSource

Length of the left-most increasing run: largest `i` such that `w[0] < w[1] < ... < w[i-1]`.

ldr :: Perm -> IntSource

Length of the left-most decreasing run: largest `i` such that `w[0] > w[1] > ... > w[i-1]`.

rir :: Perm -> IntSource

Length of the right-most increasing run: largest `i` such that `w[n-i] < ... < w[n-2] < w[n-1]`.

rdr :: Perm -> IntSource

Length of the right-most decreasing run: largest `i` such that `w[n-i] > ... > w[n-2] > w[n-1]`.

The number of components. E.g., `[2,0,3,1,4,6,7,5]` has three components: `[2,0,3,1]`, `[4]` and `[6,7,5]`.

The number of skew components. E.g., `[5,7,4,6,3,1,0,2]` has three skew components: `[5,7,4,6]`, `[3]` and `[1,0,2]`.

ep :: Perm -> IntSource

The rank as defined by Elizalde and Pak [Bijections for refined restricted permutations, J. Comb. Theory, Ser. A, 2004]:

``` maximum [ k | k <- [0..n-1], w[i] >= k for all i < k ]
```

dim :: Perm -> IntSource

The dimension of a permutation is defined as the largest non-fixed-point, or zero if all points are fixed.

The number of small ascents. A small ascent in `w` is an index `i` such that `w[i] + 1 == w[i+1]`.

The number of small descents. A small descent in `w` is an index `i` such that `w[i] == w[i+1] + 1`.