sym-0.6: Permutations, patterns, and statistics

MaintainerAnders Claesson <anders.claesson@gmail.com>
Safe HaskellNone

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

scomp :: Perm a => a -> IntSource

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

shad :: Perm a => a -> IntSource

The size of the shadow of w. That is, the number of different one point deletions of w.