sym-0.3: Permutations, patterns, and statistics

Maintainer Anders Claesson None

Math.Sym.Stat

Description

Common permutation statistics. Please contact the maintainer if you feel that there is a statistic that is missing; even better, send a patch or make a pull request.

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

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

For any permutation statistic `f`, below, it holds that ```f w == f (st w)```, and therefore the explanations below will be done on standard permutations for convenience.

Synopsis

# Documentation

asc :: Perm a => a -> IntSource

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

des :: Perm a => a -> IntSource

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

exc :: Perm a => a -> IntSource

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

fp :: Perm a => a -> IntSource

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

cyc :: Perm a => a -> IntSource

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

inv :: Perm a => a -> IntSource

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

maj :: Perm a => a -> IntSource

The major index is the sum of descents.

comaj :: Perm a => a -> IntSource

The co-major index is the sum of descents.

peak :: Perm a => a -> IntSource

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

vall :: Perm a => a -> IntSource

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

dasc :: Perm a => a -> IntSource

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

ddes :: Perm a => a -> IntSource

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

lmin :: Perm a => a -> IntSource

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

lmax :: Perm a => a -> IntSource

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

rmin :: Perm a => a -> IntSource

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

rmax :: Perm a => a -> IntSource

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

head :: Perm a => a -> IntSource

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

last :: Perm a => a -> IntSource

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

lir :: Perm a => a -> IntSource

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

ldr :: Perm a => a -> IntSource

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

rir :: Perm a => a -> IntSource

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

rdr :: Perm a => a -> IntSource

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

comp :: Perm a => a -> IntSource

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]`.

ep :: Perm a => a -> 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 a => a -> IntSource

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

asc0 :: Perm a => a -> IntSource

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

des0 :: Perm a => a -> IntSource

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

lminValues :: Perm a => a -> [Int]Source

The list of values of left-to-right minima

lminIndices :: Perm a => a -> [Int]Source

The list of indices of left-to-right minima