Sym.Perm.Stat

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

import qualified Sym.Perm.Stat as S

Documentation

asc :: Perm -> Int

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

des :: Perm -> Int

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

exc :: Perm -> Int

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

fp :: Perm -> Int

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

sfp :: Perm -> Int

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

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

inv :: Perm -> Int

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

maj :: Perm -> Int

The major index is the sum of descents.

comaj :: Perm -> Int

The co-major index is the sum of descents.

peak :: Perm -> Int

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

vall :: Perm -> Int

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

dasc :: Perm -> Int

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

ddes :: Perm -> Int

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

lmin :: Perm -> Int

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

lmax :: Perm -> Int

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

rmin :: Perm -> Int

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

rmax :: Perm -> Int

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

head :: Perm -> Int

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

last :: Perm -> Int

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

lir :: Perm -> Int

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

ldr :: Perm -> Int

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

rir :: Perm -> Int

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

rdr :: Perm -> Int

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

comp :: Perm -> Int

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

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

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

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

asc0 :: Perm -> Int

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

des0 :: Perm -> Int

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

lis :: Perm -> Int

The longest increasing subsequence.

lds :: Perm -> Int

The longest decreasing subsequence.