Maintainer | Anders Claesson <anders.claesson@gmail.com> |
---|---|

Safe Haskell | None |

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.

- asc :: Perm a => a -> Int
- des :: Perm a => a -> Int
- exc :: Perm a => a -> Int
- fp :: Perm a => a -> Int
- cyc :: Perm a => a -> Int
- inv :: Perm a => a -> Int
- maj :: Perm a => a -> Int
- comaj :: Perm a => a -> Int
- peak :: Perm a => a -> Int
- vall :: Perm a => a -> Int
- dasc :: Perm a => a -> Int
- ddes :: Perm a => a -> Int
- lmin :: Perm a => a -> Int
- lmax :: Perm a => a -> Int
- rmin :: Perm a => a -> Int
- rmax :: Perm a => a -> Int
- head :: Perm a => a -> Int
- last :: Perm a => a -> Int
- lir :: Perm a => a -> Int
- ldr :: Perm a => a -> Int
- rir :: Perm a => a -> Int
- rdr :: Perm a => a -> Int
- comp :: Perm a => a -> Int
- scomp :: Perm a => a -> Int
- ep :: Perm a => a -> Int
- dim :: Perm a => a -> Int
- asc0 :: Perm a => a -> Int
- des0 :: Perm a => a -> Int
- shad :: Perm a => a -> Int

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

.

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

.

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

.