This is Permutations.info, produced by Macaulay2, version 1.24.11

Permutations -- a package which implements permutations
*******************************************************

Description
===========

This package defines the Permutation, type. An overview of
the package's can be found in the Permutations Guide.

Author
======

  * Sean Grate (see https://seangrate.com/ ) <sean.grate@auburn.edu>

Version
=======

This documentation describes version 1.0 of Permutations.

Source code
===========

The source code from which this documentation is derived is in the file
Permutations.m2 (see common/share/Macaulay2/Permutations.m2 ). The auxiliary
files accompanying it are in the directory Permutations/ (see
common/share/Macaulay2/Permutations/ ).

Exports
=======

  * Types
      * Permutation -- the Permutation type
  * Functions and commands
      * ascendingRuns -- computes the ascending runs of a
        permutation
      * ascents -- computes the ascents of a permutation
      * avoidsPattern -- whether a permutation avoids a
        pattern
      * avoidsPatterns -- whether a permutation
        simultaneously avoids a list of patterns
      * cycleDecomposition -- computes the
        decomposition of a permutation as a product of disjoint cycles
      * cycleType -- computes the cycle type of a permutation
      * descendingRuns -- computes the descending runs
        of a permutation
      * descents -- computes the descents of a permutation
      * exceedances -- computes the exceedances of a
        permutation
      * fixedPoints -- computes the fixed points of a
        permutation
      * foataBijection -- computes the image of a
        permutation under the Foata bijection
      * inversions -- computes the inversions of a
        permutation
      * isCartwrightSturmfels -- whether a
        permutation is Cartwright-Sturmfels
      * isCDG -- whether a permutation is CDG.
      * isDerangement -- whether a permutation is a
        derangement
      * isEven -- whether a permutation is even
      * isOdd -- whether a permutation is odd
      * isVexillary -- whether a permutation is vexillary
      * ord -- computes the order of a permutation
      * permutation (missing documentation)
      * records -- computes the saliances of a permutation
      * saliances -- computes the saliances of a permutation
      * sign -- computes the sign of a permutation
  * Methods
      * "ascendingRuns(Permutation)" -- see ascendingRuns,
        -- computes the ascending runs of a permutation
      * "ascents(Permutation)" -- see ascents, -- computes the
        ascents of a permutation
      * "avoidsPattern(Permutation,List)" -- see avoidsPattern,
        -- whether a permutation avoids a pattern
      * "avoidsPatterns(Permutation,List)" -- see avoidsPatterns,
        -- whether a permutation simultaneously avoids a list
        of patterns
      * "cycleDecomposition(Permutation)" -- see cycleDecomposition,
        -- computes the decomposition of a permutation as a
        product of disjoint cycles
      * "cycleType(Permutation)" -- see cycleType, -- computes
        the cycle type of a permutation
      * "descendingRuns(Permutation)" -- see descendingRuns,
        -- computes the descending runs of a permutation
      * "descents(Permutation)" -- see descents, -- computes
        the descents of a permutation
      * "exceedances(Permutation)" -- see exceedances, --
        computes the exceedances of a permutation
      * expression(Permutation) (missing documentation)
      * "extend(Permutation,ZZ)" -- see extend, -- rewrites a
        permutation as a permution on more symbols
      * extend(Permutation,Permutation)
        -- rewrites two permutations to
        be permutations on the same number of symbols
      * "fixedPoints(Permutation)" -- see fixedPoints, --
        computes the fixed points of a permutation
      * "foataBijection(Permutation)" -- see foataBijection,
        -- computes the image of a permutation under the Foata
        bijection
      * html(Permutation) (missing documentation)
      * inverse(Permutation) -- computes the
        inverse of a permutation
      * "inversions(Permutation)" -- see inversions, --
        computes the inversions of a permutation
      * "isCartwrightSturmfels(Permutation)" -- see
        isCartwrightSturmfels, -- whether a permutation
        is Cartwright-Sturmfels
      * "isCDG(Permutation)" -- see isCDG, -- whether a
        permutation is CDG.
      * "isDerangement(Permutation)" -- see isDerangement,
        -- whether a permutation is a derangement
      * "isEven(Permutation)" -- see isEven, -- whether a
        permutation is even
      * "isOdd(Permutation)" -- see isOdd, -- whether a
        permutation is odd
      * "isVexillary(Permutation)" -- see isVexillary, --
        whether a permutation is vexillary
      * isWellDefined(Permutation), --
        checks if a list is a valid permutation
      * length(Permutation) -- computes the
        length of a permutation
      * Matrix * Permutation -- computes the
        action of a permutation on the columns of a matrix
      * Matrix ^ Permutation -- computes the
        action of a permutation on a matrix
      * Matrix _ Permutation -- computes the
        action of a permutation on the rows of a matrix
      * matrix(Permutation) -- computes the
        matrix representation of a permutation
      * new Permutation from VisibleList (missing documentation)
      * "ord(Permutation)" -- see ord, -- computes the order of a
        permutation
      * "permutation(VisibleList)" -- see Permutation, --
        the Permutation type
      * Permutation * Matrix -- computes the
        action of a permutation on the rows of a matrix
      * Permutation * Permutation, --
        computes the product of two permutations
      * Permutation * VisibleList, --
        computes the action of a permutation on a list
      * Permutation == Permutation, --
        whether two permutations are the same
      * Permutation ^ ZZ -- computes the power of a
        permutation
      * Permutation _ List -- selects a subset of
        the permutation when regarded as a list
      * Permutation _ Sequence -- selects a
        subset of the permutation when regarded as a list
      * Permutation _ ZZ -- selects an element from
        the permutation when regarded as a list
      * "records(Permutation)" -- see records, -- computes the
        saliances of a permutation
      * "saliances(Permutation)" -- see saliances, -- computes
        the saliances of a permutation
      * "sign(Permutation)" -- see sign, -- computes the sign of a
        permutation
      * tex(Permutation) (missing documentation)
      * toString(Permutation) (missing documentation)
      * "trim(Permutation)" -- see trim, -- rewrites a permutation
        in its smallest representation
      * VisibleList _ Permutation, --
        computes the action of a permutation on a list
  * Symbols
      * Weak (missing documentation)

For the programmer
==================

The object Permutations, is a package (Macaulay2Doc).

ascendingRuns -- computes the ascending runs of a permutation
*************************************************************

Synopsis
========

  * Usage:
        ascendingRuns w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * allRuns, a list (Macaulay2Doc),

Description
===========

An ascending run is a maximal subsequence of successive ascents.

+----------------------------------+
|i1 : p = permutation {3,1,2,5,4}  |
|                                  |
|o1 = Permutation{3, 1, 2, 5, 4}   |
|                                  |
|o1 : Permutation                  |
+----------------------------------+
|i2 : ascendingRuns p              |
|                                  |
|o2 = {1 : (3), (1, 2, 5), 1 : (4)}|
|                                  |
|o2 : List                         |
+----------------------------------+

See also
========

  * ascents -- computes the ascents of a permutation
  * descendingRuns -- computes the descending runs of a
    permutation
  * descents -- computes the descents of a permutation
  * exceedances -- computes the exceedances of a
    permutation
  * saliances -- computes the saliances of a permutation
  * records -- computes the saliances of a permutation

Ways to use ascendingRuns:
==========================

  * "ascendingRuns(Permutation)"

For the programmer
==================

The object ascendingRuns, is a method function (Macaulay2Doc).

ascents -- computes the ascents of a permutation
************************************************

Synopsis
========

  * Usage:
        ascents w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a list (Macaulay2Doc),

Description
===========

A permutation $p=(p_1 \, \dots \, p_n)$ has an ascent at $i$ (for $i < n$) if
$p(i) < p(i+1)$.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : ascents p                  |
|                                |
|o2 = {2, 3}                     |
|                                |
|o2 : List                       |
+--------------------------------+

See also
========

  * ascendingRuns -- computes the ascending runs of a
    permutation
  * descendingRuns -- computes the descending runs of a
    permutation
  * descents -- computes the descents of a permutation
  * exceedances -- computes the exceedances of a
    permutation
  * saliances -- computes the saliances of a permutation
  * records -- computes the saliances of a permutation

Ways to use ascents:
====================

  * "ascents(Permutation)"

For the programmer
==================

The object ascents, is a method function (Macaulay2Doc).

avoidsPattern -- whether a permutation avoids a pattern
*******************************************************

Synopsis
========

  * Usage:
        avoidsPattern(w, pattern)
  * Inputs:
      * w, a permutation,
      * pattern, a list (Macaulay2Doc),
  * Outputs:
      * isAvoiding, a Boolean value (Macaulay2Doc),

Description
===========

Pattern avoidance is more easily understood through an example. A permutation
$p$ is $2143$-avoiding if there do not exist indices $i < j < k < l$ such that
$w_j < w_i < w_l < w_k$.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : avoidsPattern(p, {2,1,4,3})|
|                                |
|o2 = false                      |
+--------------------------------+

See also
========

  * avoidsPatterns -- whether a permutation
    simultaneously avoids a list of patterns
  * isCartwrightSturmfels -- whether a
    permutation is Cartwright-Sturmfels
  * isCDG -- whether a permutation is CDG.
  * isVexillary -- whether a permutation is vexillary

Ways to use avoidsPattern:
==========================

  * "avoidsPattern(Permutation,List)"

For the programmer
==================

The object avoidsPattern, is a method function (Macaulay2Doc).

avoidsPatterns -- whether a permutation simultaneously avoids a list of patterns
********************************************************************************

Synopsis
========

  * Usage:
        avoidsPatterns(w, patterns)
  * Inputs:
      * w, a permutation,
      * patterns, a list (Macaulay2Doc),
  * Outputs:
      * a Boolean value (Macaulay2Doc),

Description
===========

See avoidsPattern, for more information on pattern
avoidance.

+----------------------------------------------+
|i1 : p = permutation {3,1,2,5,4}              |
|                                              |
|o1 = Permutation{3, 1, 2, 5, 4}               |
|                                              |
|o1 : Permutation                              |
+----------------------------------------------+
|i2 : avoidsPatterns(p, {{2,1,4,3}, {1,4,3,2}})|
|                                              |
|o2 = false                                    |
+----------------------------------------------+

See also
========

  * avoidsPattern -- whether a permutation avoids a
    pattern
  * isCartwrightSturmfels -- whether a
    permutation is Cartwright-Sturmfels
  * isCDG -- whether a permutation is CDG.
  * isVexillary -- whether a permutation is vexillary

Ways to use avoidsPatterns:
===========================

  * "avoidsPatterns(Permutation,List)"

For the programmer
==================

The object avoidsPatterns, is a method function (Macaulay2Doc).

cycleDecomposition -- computes the decomposition of a permutation as a product of disjoint cycles
*************************************************************************************************

Synopsis
========

  * Usage:
        cycleDecomposition w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a list (Macaulay2Doc),

Description
===========

Every permutation can be decomposed into a product of disjoint cycles. We
follow the convention to write the decomposition in its "canonical" or
"standard" form. So

1. each cycle is listed with its largest element first, and  2. the cycles are
listed in increasing order.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : cycleDecomposition p       |
|                                |
|o2 = {(3, 2, 1), (5, 4)}        |
|                                |
|o2 : List                       |
+--------------------------------+

See also
========

  * cycleType -- computes the cycle type of a permutation

Ways to use cycleDecomposition:
===============================

  * "cycleDecomposition(Permutation)"

For the programmer
==================

The object cycleDecomposition, is a method function (Macaulay2Doc).

cycleType -- computes the cycle type of a permutation
*****************************************************

Synopsis
========

  * Usage:
        cycleType w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a sequence (Macaulay2Doc),

Description
===========

A permutation's cycle type is the sequence consisting of the lengths of the
cycles in its cycle decomposition, listed in weakly decreasing order.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : cycleType p                |
|                                |
|o2 = (3, 2)                     |
|                                |
|o2 : Sequence                   |
+--------------------------------+

See also
========

  * cycleDecomposition -- computes the decomposition
    of a permutation as a product of disjoint cycles

Ways to use cycleType:
======================

  * "cycleType(Permutation)"

For the programmer
==================

The object cycleType, is a method function (Macaulay2Doc).

descendingRuns -- computes the descending runs of a permutation
***************************************************************

Synopsis
========

  * Usage:
        descendingRuns w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * allRuns, a list (Macaulay2Doc),

Description
===========

A descending run is a maximal subsequence of successive descents.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : descendingRuns p           |
|                                |
|o2 = {(3, 1), 1 : (2), (5, 4)}  |
|                                |
|o2 : List                       |
+--------------------------------+

See also
========

  * ascendingRuns -- computes the ascending runs of a
    permutation
  * ascents -- computes the ascents of a permutation
  * descents -- computes the descents of a permutation
  * exceedances -- computes the exceedances of a
    permutation
  * saliances -- computes the saliances of a permutation
  * records -- computes the saliances of a permutation

Ways to use descendingRuns:
===========================

  * "descendingRuns(Permutation)"

For the programmer
==================

The object descendingRuns, is a method function (Macaulay2Doc).

descents -- computes the descents of a permutation
**************************************************

Synopsis
========

  * Usage:
        descents w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a list (Macaulay2Doc),

Description
===========

A permutation $p=(p_1 \, \dots \, p_n)$ has a descent at $i$ (for $i < n$) if
$p(i) > p(i+1)$.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : descents p                 |
|                                |
|o2 = {1, 4}                     |
|                                |
|o2 : List                       |
+--------------------------------+

See also
========

  * ascendingRuns -- computes the ascending runs of a
    permutation
  * ascents -- computes the ascents of a permutation
  * descendingRuns -- computes the descending runs of a
    permutation
  * exceedances -- computes the exceedances of a
    permutation
  * saliances -- computes the saliances of a permutation
  * records -- computes the saliances of a permutation

Ways to use descents:
=====================

  * "descents(Permutation)"

For the programmer
==================

The object descents, is a method function (Macaulay2Doc).

exceedances -- computes the exceedances of a permutation
********************************************************

Synopsis
========

  * Usage:
        exceedances w
        exceedances(w, Weak)
  * Inputs:
      * w, a permutation,
  * Optional inputs (Macaulay2Doc),:
      * Weak (missing documentation) => ..., default value false,
  * Outputs:
      * a list (Macaulay2Doc),

Description
===========

A permutation $p=(p_1 \, \dots \, p_n)$ has an exceedance at $i$ if $p(i) > i$.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : exceedances p              |
|                                |
|o2 = {1, 4}                     |
|                                |
|o2 : List                       |
+--------------------------------+

This is called a weak exceedance if the inequality is not strict, i.e., $p(i)
\geq i$.

+--------------------------------+
|i3 : p = permutation {3,1,2,5,4}|
|                                |
|o3 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o3 : Permutation                |
+--------------------------------+
|i4 : exceedances(p, Weak=>true) |
|                                |
|o4 = {1, 4}                     |
|                                |
|o4 : List                       |
+--------------------------------+

See also
========

  * ascendingRuns -- computes the ascending runs of a
    permutation
  * ascents -- computes the ascents of a permutation
  * descendingRuns -- computes the descending runs of a
    permutation
  * descents -- computes the descents of a permutation
  * saliances -- computes the saliances of a permutation
  * records -- computes the saliances of a permutation

Ways to use exceedances:
========================

  * "exceedances(Permutation)"

For the programmer
==================

The object exceedances, is a method function with options (Macaulay2Doc).

extend -- rewrites a permutation as a permution on more symbols
***************************************************************

Synopsis
========

  * Usage:
        extend(w,n)
  * Inputs:
      * w, a permutation,
      * n, an integer (Macaulay2Doc),
  * Optional inputs (Macaulay2Doc),:
      * Verify (Macaulay2Doc),
        => ..., default value true,
  * Outputs:
      * a permutation,

Description
===========

A permutation on $n$ symbols is an element of the symmetric group on $n$
symbols, $\mathfrak{S}_n$. However, it can also be regarded as a permutation on
$N > n$ symbols as well by fixing the $(n+1)$st through $N$th symbols.

+-------------------------------------+
|i1 : p = permutation {3,1,2,5,4}     |
|                                     |
|o1 = Permutation{3, 1, 2, 5, 4}      |
|                                     |
|o1 : Permutation                     |
+-------------------------------------+
|i2 : extend(p, 7)                    |
|                                     |
|o2 = Permutation{3, 1, 2, 5, 4, 6, 7}|
|                                     |
|o2 : Permutation                     |
+-------------------------------------+

See also
========

  * trim (Macaulay2Doc) -- minimize generators and relations

Ways to use extend:
===================

  * "extend(Permutation,ZZ)"
  * extend(ChainComplex,ChainComplex,Matrix) (Macaulay2Doc)
    -- extend a
    module map to a chain map, if possible
  * extend(Permutation,Permutation)
    -- rewrites two permutations to be
    permutations on the same number of symbols

For the programmer
==================

The object extend (Macaulay2Doc), is a method function with options (Macaulay2Doc).

extend(Permutation,Permutation) -- rewrites two permutations to be permutations on the same number of symbols
*************************************************************************************************************

Synopsis
========

  * Function: extend (Macaulay2Doc),
  * Usage:
        e = extend(w,v)
  * Inputs:
      * w, a permutation,
      * v, a permutation,
  * Optional inputs (Macaulay2Doc),:
      * Verify (Macaulay2Doc),
        => ..., default value true,
  * Outputs:
      * e, a sequence (Macaulay2Doc),

Description
===========

For ease, we can also extend two permutations so that they are regarded as
permutations on the same number of symbols. More precisely, if we have
permutations $p=(p_1, \dots, p_n)$ and $q=(q_1, \dots, q_m)$, then extend(p,q)
will return both $p$ and $q$ as permutations on $\text{max}(m,n)$ symbols.

+-------------------------------------------------------------------------+
|i1 : p = permutation {3,1,2,5,4}                                         |
|                                                                         |
|o1 = Permutation{3, 1, 2, 5, 4}                                          |
|                                                                         |
|o1 : Permutation                                                         |
+-------------------------------------------------------------------------+
|i2 : q = permutation {2,3,1,4,5,7,6}                                     |
|                                                                         |
|o2 = Permutation{2, 3, 1, 4, 5, 7, 6}                                    |
|                                                                         |
|o2 : Permutation                                                         |
+-------------------------------------------------------------------------+
|i3 : extend(p,q)                                                         |
|                                                                         |
|o3 = (Permutation{3, 1, 2, 5, 4, 6, 7}, Permutation{2, 3, 1, 4, 5, 7, 6})|
|                                                                         |
|o3 : Sequence                                                            |
+-------------------------------------------------------------------------+

See also
========

  * extend(Permutation,ZZ) -- rewrites a permutation as a
    permution on more symbols
  * trim (Macaulay2Doc) -- minimize generators and relations

Ways to use this method:
========================

  * extend(Permutation,Permutation)
    -- rewrites two permutations to be
    permutations on the same number of symbols

fixedPoints -- computes the fixed points of a permutation
*********************************************************

Synopsis
========

  * Usage:
        fixedPoints w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a list (Macaulay2Doc),

Description
===========

A permutation $p$ has a fixed point at $i$ if $p(i) = i$. fixedPoints computes
all of the fixed points of a permutation.

+--------------------------------+
|i1 : p = permutation {2,1,3,5,4}|
|                                |
|o1 = Permutation{2, 1, 3, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : fixedPoints p              |
|                                |
|o2 = {3}                        |
|                                |
|o2 : List                       |
+--------------------------------+

See also
========

  * isDerangement -- whether a permutation is a
    derangement

Ways to use fixedPoints:
========================

  * "fixedPoints(Permutation)"

For the programmer
==================

The object fixedPoints, is a method function (Macaulay2Doc).

foataBijection -- computes the image of a permutation under the Foata bijection
*******************************************************************************

Synopsis
========

  * Usage:
        foataBijection w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a permutation,

Description
===========

Foata's fundamental bijection is a bijection between a permutation's standard
cycle decomposition and another permutation read the same (in one-line
notation) as the decomposition with its parentheses removed. For example, if $p
= (3 \, 2 \, 1)(5 \, 4)$ (written in cycle notation), then its corresponding
permutation (written in one-line notation) is $\hat{p} = (3 \, 2 \, 1 \, 5 \,
4)$.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : foataBijection p           |
|                                |
|o2 = Permutation{3, 2, 1, 5, 4} |
|                                |
|o2 : Permutation                |
+--------------------------------+

Ways to use foataBijection:
===========================

  * "foataBijection(Permutation)"

For the programmer
==================

The object foataBijection, is a method function (Macaulay2Doc).

inverse(Permutation) -- computes the inverse of a permutation
*************************************************************

Synopsis
========

  * Function: inverse (Macaulay2Doc),
  * Usage:
        inverse w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a permutation,

Description
===========

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : fixedPoints p              |
|                                |
|o2 = {}                         |
|                                |
|o2 : List                       |
+--------------------------------+

Ways to use this method:
========================

  * inverse(Permutation) -- computes the
    inverse of a permutation

inversions -- computes the inversions of a permutation
******************************************************

Synopsis
========

  * Usage:
        inversions w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a list (Macaulay2Doc),

Description
===========

A permutation $p$ has an inversion $(i,j)$ if $i < j$ and $p(i) > p(j)$.
inversions computes all of the inversions of a permutation.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : inversions p               |
|                                |
|o2 = {{1, 2}, {1, 3}, {4, 5}}   |
|                                |
|o2 : List                       |
+--------------------------------+

See also
========

  * length (Macaulay2Doc) -- length of an object

Ways to use inversions:
=======================

  * "inversions(Permutation)"

For the programmer
==================

The object inversions, is a method function (Macaulay2Doc).

isCartwrightSturmfels -- whether a permutation is Cartwright-Sturmfels
**********************************************************************

Synopsis
========

  * Usage:
        isVexillary w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a Boolean value (Macaulay2Doc),

Description
===========

A permutation $p$ is Cartwright-Sturmfels if it avoids.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : isCartwrightSturmfels p    |
|                                |
|o2 = true                       |
+--------------------------------+

See also
========

  * avoidsPattern -- whether a permutation avoids a
    pattern
  * avoidsPatterns -- whether a permutation
    simultaneously avoids a list of patterns
  * isCDG -- whether a permutation is CDG.
  * isVexillary -- whether a permutation is vexillary

Ways to use isCartwrightSturmfels:
==================================

  * "isCartwrightSturmfels(Permutation)"

For the programmer
==================

The object isCartwrightSturmfels, is a
method function (Macaulay2Doc).

isCDG -- whether a permutation is CDG.
**************************************

Synopsis
========

  * Usage:
        isCDG w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a Boolean value (Macaulay2Doc),

Description
===========

A permutation $p$ is CDG if it avoids.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : isCDG p                    |
|                                |
|o2 = true                       |
+--------------------------------+

See also
========

  * avoidsPattern -- whether a permutation avoids a
    pattern
  * avoidsPatterns -- whether a permutation
    simultaneously avoids a list of patterns
  * isCartwrightSturmfels -- whether a
    permutation is Cartwright-Sturmfels
  * isVexillary -- whether a permutation is vexillary

Ways to use isCDG:
==================

  * "isCDG(Permutation)"

For the programmer
==================

The object isCDG, is a method function (Macaulay2Doc).

isDerangement -- whether a permutation is a derangement
*******************************************************

Synopsis
========

  * Usage:
        fixedPoints w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a Boolean value (Macaulay2Doc),

Description
===========

A permutation $p$ is a derangement if it has no fixed points.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : isDerangement p            |
|                                |
|o2 = true                       |
+--------------------------------+

See also
========

  * fixedPoints -- computes the fixed points of a
    permutation

Ways to use isDerangement:
==========================

  * "isDerangement(Permutation)"

For the programmer
==================

The object isDerangement, is a method function (Macaulay2Doc).

isEven -- whether a permutation is even
***************************************

Synopsis
========

  * Usage:
        isEven w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a Boolean value (Macaulay2Doc),

Description
===========

A permutation $p$ is even if it can be written as a product of an even number
of transpositions. Equivalently, a permutation is even if its sign,
is $1$.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : isEven p                   |
|                                |
|o2 = false                      |
+--------------------------------+

See also
========

  * isOdd -- whether a permutation is odd
  * sign -- computes the sign of a permutation

Ways to use isEven:
===================

  * "isEven(Permutation)"

For the programmer
==================

The object isEven, is a method function (Macaulay2Doc).

isOdd -- whether a permutation is odd
*************************************

Synopsis
========

  * Usage:
        isOdd w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a Boolean value (Macaulay2Doc),

Description
===========

A permutation $p$ is odd if it can be written as a product of an odd number of
transpositions. Equivalently, a permutation is odd if its sign, is
$-1$.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : isOdd p                    |
|                                |
|o2 = true                       |
+--------------------------------+

See also
========

  * isEven -- whether a permutation is even
  * sign -- computes the sign of a permutation

Ways to use isOdd:
==================

  * "isOdd(Permutation)"

For the programmer
==================

The object isOdd, is a method function (Macaulay2Doc).

isVexillary -- whether a permutation is vexillary
*************************************************

Synopsis
========

  * Usage:
        isVexillary w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a Boolean value (Macaulay2Doc),

Description
===========

A permutation $p$ is vexillary if it is $2143$-avoiding.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : isVexillary p              |
|                                |
|o2 = false                      |
+--------------------------------+

See also
========

  * avoidsPattern -- whether a permutation avoids a
    pattern
  * avoidsPatterns -- whether a permutation
    simultaneously avoids a list of patterns
  * isCartwrightSturmfels -- whether a
    permutation is Cartwright-Sturmfels
  * isCDG -- whether a permutation is CDG.

Ways to use isVexillary:
========================

  * "isVexillary(Permutation)"

For the programmer
==================

The object isVexillary, is a method function (Macaulay2Doc).

isWellDefined(Permutation) -- checks if a list is a valid permutation
*********************************************************************

Synopsis
========

  * Function: isWellDefined (Macaulay2Doc),
  * Usage:
        isWellDefined w
        isWellDefined(w)
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a Boolean value (Macaulay2Doc),

Description
===========

isWellDefined p determines if p is a valid permutation. Permutations must be
constructed from lists consisting of only the integers $1 \textemdash n$. If a
list contains any other elements or does not consist of the entire range, then
an error is thrown.

+----------------------------------------+
|i1 : isWellDefined permutation {1, 2, 3}|
|                                        |
|o1 = true                               |
+----------------------------------------+
|i2 : isWellDefined permutation {0, 1, 2}|
|                                        |
|o2 = false                              |
+----------------------------------------+
|i3 : isWellDefined permutation {1, 1, 2}|
|                                        |
|o3 = false                              |
+----------------------------------------+

Ways to use this method:
========================

  * isWellDefined(Permutation) -- checks
    if a list is a valid permutation

length(Permutation) -- computes the length of a permutation
***********************************************************

Synopsis
========

  * Function: length (Macaulay2Doc),
  * Usage:
        length w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * an integer (Macaulay2Doc),

Description
===========

The length of a permutation is the size of its inversion set.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : length p                   |
|                                |
|o2 = 3                          |
+--------------------------------+

See also
========

  * inversions -- computes the inversions of a permutation

Ways to use this method:
========================

  * length(Permutation) -- computes the length
    of a permutation

Matrix * Permutation -- computes the action of a permutation on the columns of a matrix
***************************************************************************************

Synopsis
========

  * Operator: * (Macaulay2Doc),
  * Usage:
        M * w
  * Inputs:
      * M, a matrix (Macaulay2Doc),
      * w, a permutation,
  * Outputs:
      * a matrix (Macaulay2Doc),

Description
===========

A permutation $p \in \mathfrak{S}_n$ acts on the space of $m \times n$ matrices
by permuting the columns of the matrix according to the permutation.

The permutation cannot permute more than numColumns M elements.

+-----------------------------------------+
|i1 : p = permutation {3,1,2}             |
|                                         |
|o1 = Permutation{3, 1, 2}                |
|                                         |
|o1 : Permutation                         |
+-----------------------------------------+
|i2 : A = matrix {{1,2,3},{4,5,6},{7,8,9}}|
|                                         |
|o2 = | 1 2 3 |                           |
|     | 4 5 6 |                           |
|     | 7 8 9 |                           |
|                                         |
|              3       3                  |
|o2 : Matrix ZZ  <-- ZZ                   |
+-----------------------------------------+
|i3 : A * p                               |
|                                         |
|o3 = | 2 3 1 |                           |
|     | 5 6 4 |                           |
|     | 8 9 7 |                           |
|                                         |
|              3       3                  |
|o3 : Matrix ZZ  <-- ZZ                   |
+-----------------------------------------+

The permutation can be a permutation on less than numColumns M elements.

+---------------------------------+
|i4 : p = permutation {2,1}       |
|                                 |
|o4 = Permutation{2, 1}           |
|                                 |
|o4 : Permutation                 |
+---------------------------------+
|i5 : A = matrix {{1,2,3},{4,5,6}}|
|                                 |
|o5 = | 1 2 3 |                   |
|     | 4 5 6 |                   |
|                                 |
|              2       3          |
|o5 : Matrix ZZ  <-- ZZ           |
+---------------------------------+
|i6 : A * p                       |
|                                 |
|o6 = | 2 1 3 |                   |
|     | 5 4 6 |                   |
|                                 |
|              2       3          |
|o6 : Matrix ZZ  <-- ZZ           |
+---------------------------------+

See also
========

  * Matrix ^ Permutation -- computes the action of
    a permutation on a matrix

Ways to use this method:
========================

  * Matrix * Permutation -- computes the action
    of a permutation on the columns of a matrix

Matrix ^ Permutation -- computes the action of a permutation on a matrix
************************************************************************

Synopsis
========

  * Operator: ^ (Macaulay2Doc),
  * Usage:
        M^w
  * Inputs:
      * M, a matrix (Macaulay2Doc),
      * w, a permutation,
  * Outputs:
      * a matrix (Macaulay2Doc),

Description
===========

A permutation $p \in \mathfrak{S}_n$ acts on the space of $m \times n$ matrices
by permuting the columns of the matrix according to the permutation.

The permutation cannot permute more than numColumns M elements.

+-----------------------------------------+
|i1 : p = permutation {3,1,2}             |
|                                         |
|o1 = Permutation{3, 1, 2}                |
|                                         |
|o1 : Permutation                         |
+-----------------------------------------+
|i2 : A = matrix {{1,2,3},{4,5,6},{7,8,9}}|
|                                         |
|o2 = | 1 2 3 |                           |
|     | 4 5 6 |                           |
|     | 7 8 9 |                           |
|                                         |
|              3       3                  |
|o2 : Matrix ZZ  <-- ZZ                   |
+-----------------------------------------+
|i3 : A^p                                 |
|                                         |
|o3 = | 2 3 1 |                           |
|     | 5 6 4 |                           |
|     | 8 9 7 |                           |
|                                         |
|              3       3                  |
|o3 : Matrix ZZ  <-- ZZ                   |
+-----------------------------------------+

The permutation can be a permutation on less than numColumns M elements.

+---------------------------------+
|i4 : p = permutation {2,1}       |
|                                 |
|o4 = Permutation{2, 1}           |
|                                 |
|o4 : Permutation                 |
+---------------------------------+
|i5 : A = matrix {{1,2,3},{4,5,6}}|
|                                 |
|o5 = | 1 2 3 |                   |
|     | 4 5 6 |                   |
|                                 |
|              2       3          |
|o5 : Matrix ZZ  <-- ZZ           |
+---------------------------------+
|i6 : A^p                         |
|                                 |
|o6 = | 2 1 3 |                   |
|     | 5 4 6 |                   |
|                                 |
|              2       3          |
|o6 : Matrix ZZ  <-- ZZ           |
+---------------------------------+

See also
========

  * Matrix * Permutation -- computes the action
    of a permutation on the columns of a matrix

Ways to use this method:
========================

  * Matrix ^ Permutation -- computes the action of
    a permutation on a matrix

Matrix _ Permutation -- computes the action of a permutation on the rows of a matrix
************************************************************************************

Synopsis
========

  * Operator: _ (Macaulay2Doc),
  * Usage:
        w * M
  * Inputs:
      * M, a matrix (Macaulay2Doc),
      * w, a permutation,
  * Outputs:
      * a matrix (Macaulay2Doc),

Description
===========

A permutation $p \in \mathfrak{S}_m$ acts on the space of $m \times n$ matrices
by permuting the rows of the matrix according to the permutation.

The permutation cannot permute more than numRows M elements.

+-----------------------------------------+
|i1 : p = permutation {3,1,2}             |
|                                         |
|o1 = Permutation{3, 1, 2}                |
|                                         |
|o1 : Permutation                         |
+-----------------------------------------+
|i2 : A = matrix {{1,2,3},{4,5,6},{7,8,9}}|
|                                         |
|o2 = | 1 2 3 |                           |
|     | 4 5 6 |                           |
|     | 7 8 9 |                           |
|                                         |
|              3       3                  |
|o2 : Matrix ZZ  <-- ZZ                   |
+-----------------------------------------+
|i3 : p * A                               |
|                                         |
|o3 = | 4 5 6 |                           |
|     | 7 8 9 |                           |
|     | 1 2 3 |                           |
|                                         |
|              3       3                  |
|o3 : Matrix ZZ  <-- ZZ                   |
+-----------------------------------------+

The permutation can be a permutation on less than numRows M elements.

+-----------------------------------+
|i4 : p = permutation {2,1}         |
|                                   |
|o4 = Permutation{2, 1}             |
|                                   |
|o4 : Permutation                   |
+-----------------------------------+
|i5 : A = matrix {{1,2},{3,4},{5,6}}|
|                                   |
|o5 = | 1 2 |                       |
|     | 3 4 |                       |
|     | 5 6 |                       |
|                                   |
|              3       2            |
|o5 : Matrix ZZ  <-- ZZ             |
+-----------------------------------+
|i6 : A_p                           |
|                                   |
|o6 = | 3 4 |                       |
|     | 1 2 |                       |
|     | 5 6 |                       |
|                                   |
|              3       2            |
|o6 : Matrix ZZ  <-- ZZ             |
+-----------------------------------+

See also
========

  * Permutation * Matrix -- computes the action
    of a permutation on the rows of a matrix

Ways to use this method:
========================

  * Matrix _ Permutation -- computes the action
    of a permutation on the rows of a matrix

matrix(Permutation) -- computes the matrix representation of a permutation
**************************************************************************

Synopsis
========

  * Function: matrix (Macaulay2Doc),
  * Usage:
        matrix w
  * Inputs:
      * w, a permutation,
  * Optional inputs (Macaulay2Doc),:
      * Degree (Macaulay2Doc), => ..., default value
        null,
  * Outputs:
      * a matrix (Macaulay2Doc),

Description
===========

Every permutation $p$ on $n$ symbols can be written as an $n \times n$ matrix.
Its matrix representation has a $1$ in entry $(i,j)$ if $p(i) = j$ and $0$
otherwise.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : matrix p                   |
|                                |
|o2 = | 0 1 0 0 0 |              |
|     | 0 0 1 0 0 |              |
|     | 1 0 0 0 0 |              |
|     | 0 0 0 0 1 |              |
|     | 0 0 0 1 0 |              |
|                                |
|              5       5         |
|o2 : Matrix ZZ  <-- ZZ          |
+--------------------------------+

See also
========

  * Permutation * Matrix -- computes the action
    of a permutation on the rows of a matrix
  * Matrix * Permutation -- computes the action
    of a permutation on the columns of a matrix

Ways to use this method:
========================

  * matrix(Permutation) -- computes the matrix
    representation of a permutation

ord -- computes the order of a permutation
******************************************

Synopsis
========

  * Usage:
        ord w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * an integer (Macaulay2Doc),

Description
===========

The order of a permutation $p$ is the smallest positive integer $n$ such that
$p^n$ is the identity permutation, i.e., its order in the symmetric group.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : ord p                      |
|                                |
|o2 = 6                          |
+--------------------------------+

Ways to use ord:
================

  * "ord(Permutation)"

For the programmer
==================

The object ord, is a method function (Macaulay2Doc).

Permutation -- the Permutation type
***********************************

Description
===========

Permutations are constructed from lists. To create a permutation, use the
permutation method.

+--------------------------------+
|i1 : p = permutation {3,1,2,4,5}|
|                                |
|o1 = Permutation{3, 1, 2, 4, 5} |
|                                |
|o1 : Permutation                |
+--------------------------------+

Permutations must be constructed from lists consisting of only the integers $1
\dots n$. If a list contains any other elements or does not consist of the
entire range, then an error is thrown.

Functions and methods returning a permutation:
==============================================

  * "extend(Permutation,ZZ)" -- see extend, -- rewrites a
    permutation as a permution on more symbols
  * "foataBijection(Permutation)" -- see foataBijection,
    -- computes the image of a permutation under the Foata bijection
  * inverse(Permutation) -- computes the
    inverse of a permutation
  * "permutation(VisibleList)"
  * Permutation * Permutation -- computes
    the product of two permutations
  * Permutation ^ ZZ -- computes the power of a
    permutation
  * "trim(Permutation)" -- see trim, -- rewrites a permutation in
    its smallest representation

Methods that use a permutation:
===============================

  * "ascendingRuns(Permutation)" -- see ascendingRuns, --
    computes the ascending runs of a permutation
  * "ascents(Permutation)" -- see ascents, -- computes the
    ascents of a permutation
  * "avoidsPattern(Permutation,List)" -- see avoidsPattern,
    -- whether a permutation avoids a pattern
  * "avoidsPatterns(Permutation,List)" -- see avoidsPatterns,
    -- whether a permutation simultaneously avoids a list of
    patterns
  * "cycleDecomposition(Permutation)" -- see cycleDecomposition,
    -- computes the decomposition of a permutation as a
    product of disjoint cycles
  * "cycleType(Permutation)" -- see cycleType, -- computes the
    cycle type of a permutation
  * "descendingRuns(Permutation)" -- see descendingRuns,
    -- computes the descending runs of a permutation
  * "descents(Permutation)" -- see descents, -- computes the
    descents of a permutation
  * "exceedances(Permutation)" -- see exceedances, --
    computes the exceedances of a permutation
  * expression(Permutation) (missing documentation)
  * extend(Permutation,Permutation)
    -- rewrites two permutations to be
    permutations on the same number of symbols
  * "fixedPoints(Permutation)" -- see fixedPoints, --
    computes the fixed points of a permutation
  * html(Permutation) (missing documentation)
  * "inversions(Permutation)" -- see inversions, -- computes
    the inversions of a permutation
  * "isCartwrightSturmfels(Permutation)" -- see isCartwrightSturmfels,
    -- whether a permutation is Cartwright-Sturmfels
  * "isCDG(Permutation)" -- see isCDG, -- whether a permutation is
    CDG.
  * "isDerangement(Permutation)" -- see isDerangement, --
    whether a permutation is a derangement
  * "isEven(Permutation)" -- see isEven, -- whether a permutation
    is even
  * "isOdd(Permutation)" -- see isOdd, -- whether a permutation is
    odd
  * "isVexillary(Permutation)" -- see isVexillary, --
    whether a permutation is vexillary
  * isWellDefined(Permutation) -- checks
    if a list is a valid permutation
  * length(Permutation) -- computes the length
    of a permutation
  * Matrix * Permutation -- computes the action
    of a permutation on the columns of a matrix
  * Matrix ^ Permutation -- computes the action of
    a permutation on a matrix
  * Matrix _ Permutation -- computes the action
    of a permutation on the rows of a matrix
  * matrix(Permutation) -- computes the matrix
    representation of a permutation
  * new Permutation from VisibleList (missing documentation)
  * "ord(Permutation)" -- see ord, -- computes the order of a
    permutation
  * Permutation * Matrix -- computes the action
    of a permutation on the rows of a matrix
  * Permutation * VisibleList -- computes
    the action of a permutation on a list
  * Permutation == Permutation -- whether
    two permutations are the same
  * Permutation _ List -- selects a subset of the
    permutation when regarded as a list
  * Permutation _ Sequence -- selects a subset
    of the permutation when regarded as a list
  * Permutation _ ZZ -- selects an element from the
    permutation when regarded as a list
  * "records(Permutation)" -- see records, -- computes the
    saliances of a permutation
  * "saliances(Permutation)" -- see saliances, -- computes the
    saliances of a permutation
  * "sign(Permutation)" -- see sign, -- computes the sign of a
    permutation
  * tex(Permutation) (missing documentation)
  * toString(Permutation) (missing documentation)
  * VisibleList _ Permutation -- computes
    the action of a permutation on a list

For the programmer
==================

The object Permutation, is a type (Macaulay2Doc),
with ancestor classes VisibleList (Macaulay2Doc),
< BasicList (Macaulay2Doc) <
Thing (Macaulay2Doc).

permutation
***********

Ways to use permutation:
========================

  * "permutation(VisibleList)" -- see Permutation, -- the
    Permutation type

For the programmer
==================

The object permutation (missing documentation) is a method function (Macaulay2Doc).

Permutation * Matrix -- computes the action of a permutation on the rows of a matrix
************************************************************************************

Synopsis
========

  * Operator: * (Macaulay2Doc),
  * Usage:
        w * M
  * Inputs:
      * w, a permutation,
      * M, a matrix (Macaulay2Doc),
  * Outputs:
      * a matrix (Macaulay2Doc),

Description
===========

A permutation $p$ acts on the space of $n \times n$ matrices by permuting the
rows of the matrix according to the permutation.

The permutation cannot permute more than numRows M elements.

+-----------------------------------------+
|i1 : p = permutation {3,1,2}             |
|                                         |
|o1 = Permutation{3, 1, 2}                |
|                                         |
|o1 : Permutation                         |
+-----------------------------------------+
|i2 : A = matrix {{1,2,3},{4,5,6},{7,8,9}}|
|                                         |
|o2 = | 1 2 3 |                           |
|     | 4 5 6 |                           |
|     | 7 8 9 |                           |
|                                         |
|              3       3                  |
|o2 : Matrix ZZ  <-- ZZ                   |
+-----------------------------------------+
|i3 : p * A                               |
|                                         |
|o3 = | 4 5 6 |                           |
|     | 7 8 9 |                           |
|     | 1 2 3 |                           |
|                                         |
|              3       3                  |
|o3 : Matrix ZZ  <-- ZZ                   |
+-----------------------------------------+

The permutation can be a permutation on less than numRows M elements.

+-----------------------------------+
|i4 : p = permutation {2,1}         |
|                                   |
|o4 = Permutation{2, 1}             |
|                                   |
|o4 : Permutation                   |
+-----------------------------------+
|i5 : A = matrix {{1,2},{3,4},{5,6}}|
|                                   |
|o5 = | 1 2 |                       |
|     | 3 4 |                       |
|     | 5 6 |                       |
|                                   |
|              3       2            |
|o5 : Matrix ZZ  <-- ZZ             |
+-----------------------------------+
|i6 : p * A                         |
|                                   |
|o6 = | 3 4 |                       |
|     | 1 2 |                       |
|     | 5 6 |                       |
|                                   |
|              3       2            |
|o6 : Matrix ZZ  <-- ZZ             |
+-----------------------------------+

See also
========

  * Matrix _ Permutation -- computes the action
    of a permutation on the rows of a matrix

Ways to use this method:
========================

  * Permutation * Matrix -- computes the action
    of a permutation on the rows of a matrix

Permutation * Permutation -- computes the product of two permutations
*********************************************************************

Synopsis
========

  * Operator: * (Macaulay2Doc),
  * Usage:
        w * v
  * Inputs:
      * w, a permutation,
      * v, a permutation,
  * Outputs:
      * a permutation,

Description
===========

The product of two permutations $p$ and $q$ is given by their composition,
i.e., $ (p \circ q)(i) = p(q(i))$.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : q = permutation {2,1,3,4,5}|
|                                |
|o2 = Permutation{2, 1, 3, 4, 5} |
|                                |
|o2 : Permutation                |
+--------------------------------+
|i3 : p * q                      |
|                                |
|o3 = Permutation{1, 3, 2, 5, 4} |
|                                |
|o3 : Permutation                |
+--------------------------------+

The two permutations do not need to be the same length.

+--------------------------------+
|i4 : p = permutation {3,1,2,5,4}|
|                                |
|o4 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o4 : Permutation                |
+--------------------------------+
|i5 : q = permutation {2,1,3}    |
|                                |
|o5 = Permutation{2, 1, 3}       |
|                                |
|o5 : Permutation                |
+--------------------------------+
|i6 : p * q                      |
|                                |
|o6 = Permutation{1, 3, 2, 5, 4} |
|                                |
|o6 : Permutation                |
+--------------------------------+

Ways to use this method:
========================

  * Permutation * Permutation -- computes
    the product of two permutations

Permutation * VisibleList -- computes the action of a permutation on a list
***************************************************************************

Synopsis
========

  * Operator: * (Macaulay2Doc),
  * Usage:
        w * l
  * Inputs:
      * w, a permutation,
      * l, a visible list (Macaulay2Doc),
  * Outputs:
      * a visible list (Macaulay2Doc),

Description
===========

A permutation $p$ acts on the elements of list by permuting the elements of the
list according to the permutation. More precisely, if $L = \{ e_1, \dots, e_k
\}$ is a list and $p=(p_1, \dots, p_n)$ is a permutation, then the action is
given by $p*L = \{ e_{p(1)}, \dots, e_{p(k)}}$.

The permutation cannot permute more than #l elements.

+-------------------------------------+
|i1 : p = permutation {3,1,2,5,4,7,6} |
|                                     |
|o1 = Permutation{3, 1, 2, 5, 4, 7, 6}|
|                                     |
|o1 : Permutation                     |
+-------------------------------------+
|i2 : L = {3,1,2,5,4,6,7}             |
|                                     |
|o2 = {3, 1, 2, 5, 4, 6, 7}           |
|                                     |
|o2 : List                            |
+-------------------------------------+
|i3 : p * L                           |
|                                     |
|o3 = {2, 3, 1, 4, 5, 7, 6}           |
|                                     |
|o3 : List                            |
+-------------------------------------+

The permutation can be a permutation on less than #l elements.

+--------------------------------+
|i4 : p = permutation {3,1,2,4,5}|
|                                |
|o4 = Permutation{3, 1, 2, 4, 5} |
|                                |
|o4 : Permutation                |
+--------------------------------+
|i5 : L = {3,1,2,5,4,6,7}        |
|                                |
|o5 = {3, 1, 2, 5, 4, 6, 7}      |
|                                |
|o5 : List                       |
+--------------------------------+
|i6 : p * L                      |
|                                |
|o6 = {2, 3, 1, 5, 4, 6, 7}      |
|                                |
|o6 : List                       |
+--------------------------------+

See also
========

  * VisibleList _ Permutation -- computes
    the action of a permutation on a list

Ways to use this method:
========================

  * Permutation * VisibleList -- computes
    the action of a permutation on a list

Permutation == Permutation -- whether two permutations are the same
*******************************************************************

Synopsis
========

  * Operator: == (Macaulay2Doc),
  * Usage:
        w == v
  * Inputs:
      * w, a permutation,
      * v, a permutation,
  * Outputs:
      * a Boolean value (Macaulay2Doc),

Description
===========

Two permutations $p$ and $q$ are equal if $p(i) = q(i)$ for all $i$.

+-------------------------------------+
|i1 : p = permutation {3,1,2,5,4}     |
|                                     |
|o1 = Permutation{3, 1, 2, 5, 4}      |
|                                     |
|o1 : Permutation                     |
+-------------------------------------+
|i2 : q = permutation {3,1,2,5,4,6,7} |
|                                     |
|o2 = Permutation{3, 1, 2, 5, 4, 6, 7}|
|                                     |
|o2 : Permutation                     |
+-------------------------------------+
|i3 : p == q                          |
|                                     |
|o3 = true                            |
+-------------------------------------+

The permutations do not need to be the same length.

+----------------------------------+
|i4 : p = permutation {3,1,2,4}    |
|                                  |
|o4 = Permutation{3, 1, 2, 4}      |
|                                  |
|o4 : Permutation                  |
+----------------------------------+
|i5 : q = permutation {3,1,2,4,5,6}|
|                                  |
|o5 = Permutation{3, 1, 2, 4, 5, 6}|
|                                  |
|o5 : Permutation                  |
+----------------------------------+
|i6 : p == q                       |
|                                  |
|o6 = true                         |
+----------------------------------+

Ways to use this method:
========================

  * Permutation == Permutation -- whether
    two permutations are the same

Permutation ^ ZZ -- computes the power of a permutation
*******************************************************

Synopsis
========

  * Operator: ^ (Macaulay2Doc),
  * Usage:
        w^n
  * Inputs:
      * w, a permutation,
      * n, an integer (Macaulay2Doc),
  * Outputs:
      * a permutation,

Description
===========

Computes the power of a permutation. The power can be any integer.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : p^2                        |
|                                |
|o2 = Permutation{2, 3, 1}       |
|                                |
|o2 : Permutation                |
+--------------------------------+
|i3 : p^0                        |
|                                |
|o3 = Permutation{1, 2, 3, 4, 5} |
|                                |
|o3 : Permutation                |
+--------------------------------+
|i4 : p^(-3)                     |
|                                |
|o4 = Permutation{1, 2, 3, 5, 4} |
|                                |
|o4 : Permutation                |
+--------------------------------+

Ways to use this method:
========================

  * Permutation ^ ZZ -- computes the power of a
    permutation

Permutation _ List -- selects a subset of the permutation when regarded as a list
*********************************************************************************

Synopsis
========

  * Operator: _ (Macaulay2Doc),
  * Usage:
        w_l
  * Inputs:
      * w, a permutation,
      * l, a list (Macaulay2Doc),
  * Outputs:
      * a list (Macaulay2Doc),

Description
===========

Selects a subset of the permutation when it is regarded as a list. It is
important to note that the output may not be a valid permutation.

The indices should be 0-indexed.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : p_{1,2}                    |
|                                |
|o2 = {1, 2}                     |
|                                |
|o2 : List                       |
+--------------------------------+

See also
========

  * Permutation _ Sequence -- selects a subset
    of the permutation when regarded as a list
  * Permutation _ ZZ -- selects an element from the
    permutation when regarded as a list

Ways to use this method:
========================

  * Permutation _ List -- selects a subset of the
    permutation when regarded as a list

Permutation _ Sequence -- selects a subset of the permutation when regarded as a list
*************************************************************************************

Synopsis
========

  * Operator: _ (Macaulay2Doc),
  * Usage:
        w_s
  * Inputs:
      * w, a permutation,
      * s, a sequence (Macaulay2Doc),
  * Outputs:
      * a list (Macaulay2Doc),

Description
===========

Selects a subset of the permutation when it is regarded as a list. It is
important to note that the output may not be a valid permutation.

The indices should be 0-indexed.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : p_(1,2)                    |
|                                |
|o2 = {1, 2}                     |
|                                |
|o2 : List                       |
+--------------------------------+

See also
========

  * Permutation _ List -- selects a subset of the
    permutation when regarded as a list
  * Permutation _ ZZ -- selects an element from the
    permutation when regarded as a list

Ways to use this method:
========================

  * Permutation _ Sequence -- selects a subset
    of the permutation when regarded as a list

Permutation _ ZZ -- selects an element from the permutation when regarded as a list
***********************************************************************************

Synopsis
========

  * Operator: _ (Macaulay2Doc),
  * Usage:
        w_n
  * Inputs:
      * w, a permutation,
      * n, an integer (Macaulay2Doc),
  * Outputs:
      * an integer (Macaulay2Doc),

Description
===========

Selects an element from the permutation when it is regarded as a list. The
index should be 1-indexed.

Given a permutation $p$ and index $i$, this is the same as $p(i)$.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : p_1                        |
|                                |
|o2 = 3                          |
+--------------------------------+

Ways to use this method:
========================

  * Permutation _ ZZ -- selects an element from the
    permutation when regarded as a list

Permutations Guide -- a detailed overview of permutations in Macaulay2
**********************************************************************

This page gives an overview of the use of permutations.

The sections of the overview are, in order:

Creating permutations.  Indexing.  Basic operations.  Group actions.  Cyclic
Decompositions.  Ascents, descents, runs, exceedances, and records.  Pattern
avoidance.  Foata's fundamental bijection.  Miscellaneous.

Links to individual documentation pages for the functions described in this
article are collected in an alphabetized list at the very end of the page.

Creating permutations.

Permutations are constructed from lists. To create a permutation, use the
permutation method:

+--------------------------------+
|i1 : p = permutation {3,1,2,4,5}|
|                                |
|o1 = Permutation{3, 1, 2, 4, 5} |
|                                |
|o1 : Permutation                |
+--------------------------------+

Permutations must be constructed from lists consisting of only the integers $1
\textemdash n$. If a list contains any other elements or does not consist of
the entire range, then an error is thrown. The method matrix (Macaulay2Doc),
can be used to get the matrix representation of the
permutation. In this representation, for a permutation $p$, if $p(i)=j$, then
then the $(i,j)$th entry is $1$.

+--------------------------------+
|i2 : p = permutation {3,1,2,4,5}|
|                                |
|o2 = Permutation{3, 1, 2, 4, 5} |
|                                |
|o2 : Permutation                |
+--------------------------------+
|i3 : matrix p                   |
|                                |
|o3 = | 0 1 0 0 0 |              |
|     | 0 0 1 0 0 |              |
|     | 1 0 0 0 0 |              |
|     | 0 0 0 1 0 |              |
|     | 0 0 0 0 1 |              |
|                                |
|              5       5         |
|o3 : Matrix ZZ  <-- ZZ          |
+--------------------------------+

This is especially useful for considering the action of permutations on
matrices, see Group actions.

Basic operations.

Two permutations $p$ and $q$ are equal if they are equal as functions, i.e., if
$p(i) = q(i)$ for all $i$.

+--------------------------------+
|i4 : p = permutation {3,1,2}    |
|                                |
|o4 = Permutation{3, 1, 2}       |
|                                |
|o4 : Permutation                |
+--------------------------------+
|i5 : q = permutation {3,1,2,4,5}|
|                                |
|o5 = Permutation{3, 1, 2, 4, 5} |
|                                |
|o5 : Permutation                |
+--------------------------------+
|i6 : p == q                     |
|                                |
|o6 = true                       |
+--------------------------------+

We can also multiply (or compose) two permutations. We follow the convention of
$(p*q)(i) = p(q(i))$.

+--------------------------------+
|i7 : p = permutation {3,1,2,5,4}|
|                                |
|o7 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o7 : Permutation                |
+--------------------------------+
|i8 : q = permutation {2,1,3,4,5}|
|                                |
|o8 = Permutation{2, 1, 3, 4, 5} |
|                                |
|o8 : Permutation                |
+--------------------------------+
|i9 : p*q                        |
|                                |
|o9 = Permutation{1, 3, 2, 5, 4} |
|                                |
|o9 : Permutation                |
+--------------------------------+

This also let's us compute powers of permutations.

+---------------------------------+
|i10 : p = permutation {3,1,2,5,4}|
|                                 |
|o10 = Permutation{3, 1, 2, 5, 4} |
|                                 |
|o10 : Permutation                |
+---------------------------------+
|i11 : p^2                        |
|                                 |
|o11 = Permutation{2, 3, 1}       |
|                                 |
|o11 : Permutation                |
+---------------------------------+
|i12 : p^6                        |
|                                 |
|o12 = Permutation{1}             |
|                                 |
|o12 : Permutation                |
+---------------------------------+
|i13 : p^0                        |
|                                 |
|o13 = Permutation{1, 2, 3, 4, 5} |
|                                 |
|o13 : Permutation                |
+---------------------------------+
|i14 : p^(-1)                     |
|                                 |
|o14 = Permutation{2, 3, 1, 5, 4} |
|                                 |
|o14 : Permutation                |
+---------------------------------+
|i15 : p^(-2)                     |
|                                 |
|o15 = Permutation{3, 1, 2}       |
|                                 |
|o15 : Permutation                |
+---------------------------------+

Group actions.

A permutation on $n$ symbols acts on lists of size $n$ by permuting its
contents according to the permutation.

+----------------------------------+
|i16 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i17 : L = {1,2,3,4,5};            |
+----------------------------------+
|i18 : p*L                         |
|                                  |
|o18 = {3, 1, 2, 5, 4}             |
|                                  |
|o18 : List                        |
+----------------------------------+

A permutation $p$ on $n$ symbols can also be regarded as a permutation on $N$
symbols for any $N \geq n$ by regarding all of the indices $n+1, n+2, \dots$ as
fixed by $p$, i.e., $p(i)=i$ for all $i > n$. This is also reflected in the
group action.

+----------------------------------+
|i19 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i20 : L = {1,2,3,4,5,6,7,8};      |
+----------------------------------+
|i21 : p*L                         |
|                                  |
|o21 = {3, 1, 2, 5, 4, 6, 7, 8}    |
|                                  |
|o21 : List                        |
+----------------------------------+

In a similar manner, permutations on $n$ symbols also act on the space of $m
\times n$ matrices by permuting the rows (or columns). Another way to view this
action is via the multiplication on the left by the matrix representation of
the permutation (if acting on the rows).

+------------------------------+
|i22 : p = permutation {3,1,2};|
+------------------------------+
|i23 : M = id_(ZZ^3);          |
|                              |
|               3       3      |
|o23 : Matrix ZZ  <-- ZZ       |
+------------------------------+
|i24 : p*M                     |
|                              |
|o24 = | 0 1 0 |               |
|      | 0 0 1 |               |
|      | 1 0 0 |               |
|                              |
|               3       3      |
|o24 : Matrix ZZ  <-- ZZ       |
+------------------------------+

Just as in the case of lists, the size of the matrix can be larger than $n$.

+------------------------------+
|i25 : p = permutation {3,1,2};|
+------------------------------+
|i26 : M = id_(ZZ^5);          |
|                              |
|               5       5      |
|o26 : Matrix ZZ  <-- ZZ       |
+------------------------------+
|i27 : p*M                     |
|                              |
|o27 = | 0 1 0 0 0 |           |
|      | 0 0 1 0 0 |           |
|      | 1 0 0 0 0 |           |
|      | 0 0 0 1 0 |           |
|      | 0 0 0 0 1 |           |
|                              |
|               5       5      |
|o27 : Matrix ZZ  <-- ZZ       |
+------------------------------+

The matrix does not need to be square. As long as the number of rows is greater
than or equal largest non-fixed point of the permutation, the action is valid.

+-------------------------------------+
|i28 : p = permutation {3,1,2};       |
+-------------------------------------+
|i29 : M = id_(ZZ^3) || id_(ZZ^3);    |
|                                     |
|               6       3             |
|o29 : Matrix ZZ  <-- ZZ              |
+-------------------------------------+
|i30 : N = matrix {{1,0},{0,1},{1,1}};|
|                                     |
|               3       2             |
|o30 : Matrix ZZ  <-- ZZ              |
+-------------------------------------+
|i31 : p*M                            |
|                                     |
|o31 = | 0 1 0 |                      |
|      | 0 0 1 |                      |
|      | 1 0 0 |                      |
|      | 1 0 0 |                      |
|      | 0 1 0 |                      |
|      | 0 0 1 |                      |
|                                     |
|               6       3             |
|o31 : Matrix ZZ  <-- ZZ              |
+-------------------------------------+
|i32 : p*N                            |
|                                     |
|o32 = | 0 1 |                        |
|      | 1 1 |                        |
|      | 1 0 |                        |
|                                     |
|               3       2             |
|o32 : Matrix ZZ  <-- ZZ              |
+-------------------------------------+

We can also act on the columns of the matrix in a similar way.

+-------------------------------------------------+
|i33 : p = permutation {3,1,2};                   |
+-------------------------------------------------+
|i34 : M = id_(ZZ^3) || id_(ZZ^3);                |
|                                                 |
|               6       3                         |
|o34 : Matrix ZZ  <-- ZZ                          |
+-------------------------------------------------+
|i35 : N = matrix {{1,0,0,0},{0,1,0,0},{0,0,1,0}};|
|                                                 |
|               3       4                         |
|o35 : Matrix ZZ  <-- ZZ                          |
+-------------------------------------------------+
|i36 : M*p                                        |
|                                                 |
|o36 = | 0 0 1 |                                  |
|      | 1 0 0 |                                  |
|      | 0 1 0 |                                  |
|      | 0 0 1 |                                  |
|      | 1 0 0 |                                  |
|      | 0 1 0 |                                  |
|                                                 |
|               6       3                         |
|o36 : Matrix ZZ  <-- ZZ                          |
+-------------------------------------------------+
|i37 : N*p                                        |
|                                                 |
|o37 = | 0 0 1 0 |                                |
|      | 1 0 0 0 |                                |
|      | 0 1 0 0 |                                |
|                                                 |
|               3       4                         |
|o37 : Matrix ZZ  <-- ZZ                          |
+-------------------------------------------------+

Cycle decompositions.

Every permutation can be decomposed as a product of disjoint cycles. This can
be computed with cycleDecomposition.

+---------------------------------+
|i38 : p = permutation {3,1,2,5,4}|
|                                 |
|o38 = Permutation{3, 1, 2, 5, 4} |
|                                 |
|o38 : Permutation                |
+---------------------------------+
|i39 : cycleDecomposition p       |
|                                 |
|o39 = {(3, 2, 1), (5, 4)}        |
|                                 |
|o39 : List                       |
+---------------------------------+

We follow the convention to write the decomposition in its "canonical" or
"standard" form. So

1. each cycle is listed with its largest element first, and  2. the cycles are
listed in increasing order.

A permutation's cycle type is the sequence consisting of the lengths of the
cycles in its cycle decomposition, listed in weakly decreasing order.

+-----------------+
|i40 : cycleType p|
|                 |
|o40 = (3, 2)     |
|                 |
|o40 : Sequence   |
+-----------------+

Ascents, descents, runs, exceedances, saliances, and records.

A permutation $p=(p_1 \, \dots \, p_n)$ has an ascent at $i$ (for $i < n$) if
$p(i) < p(i+1)$. Similarly, it has a descent at $i$ (for $i < n$) if $p(i) >
p(i+1)$. We can compute the set of ascents and the set of descents using
ascents and descents, respectively.

+----------------------------------+
|i41 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i42 : ascents p                   |
|                                  |
|o42 = {2, 3}                      |
|                                  |
|o42 : List                        |
+----------------------------------+
|i43 : descents p                  |
|                                  |
|o43 = {1, 4}                      |
|                                  |
|o43 : List                        |
+----------------------------------+

An ascending run is a maximal subsequence of successive ascents. Similarly, a
descending run is a maximal subsequence of successive descents.

+-----------------------------------+
|i44 : p = permutation {3,1,2,5,4}; |
+-----------------------------------+
|i45 : ascendingRuns p              |
|                                   |
|o45 = {1 : (3), (1, 2, 5), 1 : (4)}|
|                                   |
|o45 : List                         |
+-----------------------------------+
|i46 : descendingRuns p             |
|                                   |
|o46 = {(3, 1), 1 : (2), (5, 4)}    |
|                                   |
|o46 : List                         |
+-----------------------------------+

A permutation $p=(p_1 \, \dots \, p_n)$ has an exceedance at $i$ if $p(i) > i$;
this is called a weak exceedance if the inequality is not strict, i.e., $p(i)
\geq i$.

+----------------------------------+
|i47 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i48 : exceedances p               |
|                                  |
|o48 = {1, 4}                      |
|                                  |
|o48 : List                        |
+----------------------------------+

A permutation $p$ has a saliance at $i$ if $p(j) < p(i)$ for all $j > i$.

+----------------------------------+
|i49 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i50 : saliances p                 |
|                                  |
|o50 = {4, 5}                      |
|                                  |
|o50 : List                        |
+----------------------------------+

A permutation $p$ has a record at $i$ if $p(j) < p(i)$ for all $j < i$.

+----------------------------------+
|i51 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i52 : records p                   |
|                                  |
|o52 = {1, 4}                      |
|                                  |
|o52 : List                        |
+----------------------------------+

Pattern avoidance.

We can check if a permutation avoids a pattern. For example, a permutation $p$
is $2143$-avoiding if there do not exist indices $i < j < k < l$ such that $w_j
< w_i < w_l < w_k$.

+----------------------------------+
|i53 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i54 : avoidsPattern(p, {2,1,4,3}) |
|                                  |
|o54 = false                       |
+----------------------------------+

Some patterns are common enough that those pattern-avoiding permutations are
given a name, such as vexillary for those that are $2143$-avoiding.

+----------------------------------+
|i55 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i56 : isVexillary p               |
|                                  |
|o56 = false                       |
+----------------------------------+

We can also check if a permutation simultaneously avoids a list of patterns.

+----------------------------------------------+
|i57 : p = permutation {3,1,2,5,4};            |
+----------------------------------------------+
|i58 : avoidsPatterns(p, {{2,1,4,3},{1,4,3,2}})|
|                                              |
|o58 = false                                   |
+----------------------------------------------+

Just as before, some lists of patterns are common enough to be given names. See
the documentation for isCartwrightSturmfels, and
isCDG, for such lists of patterns.

+----------------------------------+
|i59 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i60 : isCartwrightSturmfels p     |
|                                  |
|o60 = true                        |
+----------------------------------+
|i61 : isCDG p                     |
|                                  |
|o61 = true                        |
+----------------------------------+

Foata's fundamental bijection.

Foata's fundamental bijection is a bijection between a permutation's standard
cycle decomposition and another permutation read the same (in one-line
notation) as the decomposition with its parentheses removed. For example, if $p
= (3 \, 2 \, 1)(5 \, 4)$ (written in cycle notation), then its corresponding
permutation (written in one-line notation) is $\hat{p} = (3 \, 2 \, 1 \, 5 \,
4)$.

+----------------------------------+
|i62 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i63 : foataBijection p            |
|                                  |
|o63 = Permutation{3, 2, 1, 5, 4}  |
|                                  |
|o63 : Permutation                 |
+----------------------------------+

Miscellaneous.

We can compute the inverse of a permutation.

+----------------------------------+
|i64 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i65 : inverse p                   |
|                                  |
|o65 = Permutation{2, 3, 1, 5, 4}  |
|                                  |
|o65 : Permutation                 |
+----------------------------------+

The order of a permutation $p$ is its order in the symmetric group
$\mathfrak{S}_n$, i.e., the smallest positive integer $k$ such that $p^k$ is
the identity permutation.

+----------------------------------+
|i66 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i67 : ord p                       |
|                                  |
|o67 = 6                           |
+----------------------------------+

Every permutation can be written as a product of transpositions. One definition
for the sign of a permutation $p$ is $1$ if it can be written as a product of
an even number of transpositions and is $-1$ if it can be written as an odd
number of transpositions. If $\text{sign}(p) = 1$, the permutation is called
even and if $\text{sign}(p) = -1 $, it is called pdd.

+----------------------------------+
|i68 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i69 : sign p                      |
|                                  |
|o69 = -1                          |
+----------------------------------+
|i70 : isEven p                    |
|                                  |
|o70 = false                       |
+----------------------------------+
|i71 : isOdd p                     |
|                                  |
|o71 = true                        |
+----------------------------------+

A permutation $p$ is a derangement if $p(i) \neq i$ for all $i$. We can
determine if $p$ is a derangement as well its fixed points.

+----------------------------------+
|i72 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i73 : isDerangement p             |
|                                  |
|o73 = true                        |
+----------------------------------+
|i74 : fixedPoints p               |
|                                  |
|o74 = {}                          |
|                                  |
|o74 : List                        |
+----------------------------------+

A permutation $p$ has an inversion $(i,j)$ if $i < j$ and $p(i) > p(j)$. We can
compute all the inversions of a permutation.

+----------------------------------+
|i75 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i76 : inversions p                |
|                                  |
|o76 = {{1, 2}, {1, 3}, {4, 5}}    |
|                                  |
|o76 : List                        |
+----------------------------------+

See also
========

  * Permutation _ ZZ -- selects an element from the
    permutation when regarded as a list
  * Permutation _ List -- selects a subset of the
    permutation when regarded as a list
  * Permutation _ Sequence -- selects a subset
    of the permutation when regarded as a list
  * VisibleList _ Permutation -- computes
    the action of a permutation on a list
  * Permutation == Permutation -- whether
    two permutations are the same
  * Permutation * VisibleList -- computes
    the action of a permutation on a list
  * Permutation * Matrix -- computes the action
    of a permutation on the rows of a matrix
  * Matrix * Permutation -- computes the action
    of a permutation on the columns of a matrix
  * Matrix _ Permutation -- computes the action
    of a permutation on the rows of a matrix
  * Matrix ^ Permutation -- computes the action of
    a permutation on a matrix
  * Permutation * Permutation -- computes
    the product of two permutations
  * Permutation ^ ZZ -- computes the power of a
    permutation
  * ascendingRuns -- computes the ascending runs of a
    permutation
  * ascents -- computes the ascents of a permutation
  * avoidsPattern -- whether a permutation avoids a
    pattern
  * avoidsPatterns -- whether a permutation
    simultaneously avoids a list of patterns
  * cycleDecomposition -- computes the decomposition
    of a permutation as a product of disjoint cycles
  * cycleType -- computes the cycle type of a permutation
  * descendingRuns -- computes the descending runs of a
    permutation
  * descents -- computes the descents of a permutation
  * exceedances -- computes the exceedances of a
    permutation
  * extend (Macaulay2Doc) -- extend a module map to a chain map,
    if possible
  * fixedPoints -- computes the fixed points of a
    permutation
  * foataBijection -- computes the image of a
    permutation under the Foata bijection
  * inverse (Macaulay2Doc) -- compute the inverse
  * inversions -- computes the inversions of a permutation
  * isCartwrightSturmfels -- whether a
    permutation is Cartwright-Sturmfels
  * isCDG -- whether a permutation is CDG.
  * isDerangement -- whether a permutation is a
    derangement
  * isEven -- whether a permutation is even
  * isOdd -- whether a permutation is odd
  * isWellDefined (Macaulay2Doc) -- whether a map is well
    defined
  * isVexillary -- whether a permutation is vexillary
  * ord -- computes the order of a permutation
  * records -- computes the saliances of a permutation
  * trim (Macaulay2Doc) -- minimize generators and relations
  * saliances -- computes the saliances of a permutation
  * sign -- computes the sign of a permutation
  * matrix(Permutation) -- computes the matrix
    representation of a permutation

records -- computes the saliances of a permutation
**************************************************

Synopsis
========

  * Usage:
        records w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a list (Macaulay2Doc),

Description
===========

A permutation $p$ has a record at $i$ if $p(j) < p(i)$ for all $j < i$.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : saliances p                |
|                                |
|o2 = {4, 5}                     |
|                                |
|o2 : List                       |
+--------------------------------+

See also
========

  * ascendingRuns -- computes the ascending runs of a
    permutation
  * ascents -- computes the ascents of a permutation
  * descendingRuns -- computes the descending runs of a
    permutation
  * descents -- computes the descents of a permutation
  * exceedances -- computes the exceedances of a
    permutation
  * saliances -- computes the saliances of a permutation

Ways to use records:
====================

  * "records(Permutation)"

For the programmer
==================

The object records, is a method function (Macaulay2Doc).

saliances -- computes the saliances of a permutation
****************************************************

Synopsis
========

  * Usage:
        saliances w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * a list (Macaulay2Doc),

Description
===========

A permutation $p$ has a saliance at $i$ if $p(j) < p(i)$ for all $j > i$.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : saliances p                |
|                                |
|o2 = {4, 5}                     |
|                                |
|o2 : List                       |
+--------------------------------+

See also
========

  * ascendingRuns -- computes the ascending runs of a
    permutation
  * ascents -- computes the ascents of a permutation
  * descendingRuns -- computes the descending runs of a
    permutation
  * descents -- computes the descents of a permutation
  * exceedances -- computes the exceedances of a
    permutation
  * records -- computes the saliances of a permutation

Ways to use saliances:
======================

  * "saliances(Permutation)"

For the programmer
==================

The object saliances, is a method function (Macaulay2Doc).

sign -- computes the sign of a permutation
******************************************

Synopsis
========

  * Usage:
        sign w
  * Inputs:
      * w, a permutation,
  * Outputs:
      * an integer (Macaulay2Doc),

Description
===========

Every permutation can be written as a product of transpositions. One definition
for the sign of a permutation $p$ is $1$ if it can be written as a product of
an even number of transpositions and is $-1$ if it can be written as an odd
number of transpositions.

+--------------------------------+
|i1 : p = permutation {3,1,2,5,4}|
|                                |
|o1 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o1 : Permutation                |
+--------------------------------+
|i2 : sign p                     |
|                                |
|o2 = -1                         |
+--------------------------------+

See also
========

  * cycleDecomposition -- computes the decomposition
    of a permutation as a product of disjoint cycles
  * cycleType -- computes the cycle type of a permutation
  * isEven -- whether a permutation is even
  * isOdd -- whether a permutation is odd

Ways to use sign:
=================

  * "sign(Permutation)"

For the programmer
==================

The object sign, is a method function (Macaulay2Doc).

trim -- rewrites a permutation in its smallest representation
*************************************************************

Synopsis
========

  * Usage:
        trim w
  * Inputs:
      * w, a permutation,
  * Optional inputs (Macaulay2Doc),:
      * Strategy (Macaulay2Doc), => ..., default value null,
  * Outputs:
      * a permutation,

Description
===========

trim rewrites a permutation $p$ as a permutation in $S_n$, where $n$ is the
smallest integer such that $p$ is in $\mathfrak{S}_n$. In other words, it
returns a permutation where any extraneous fixed points are removed.

+-------------------------------------+
|i1 : p = permutation {3,1,2,5,4,6,7} |
|                                     |
|o1 = Permutation{3, 1, 2, 5, 4, 6, 7}|
|                                     |
|o1 : Permutation                     |
+-------------------------------------+
|i2 : trim p                          |
|                                     |
|o2 = Permutation{3, 1, 2, 5, 4}      |
|                                     |
|o2 : Permutation                     |
+-------------------------------------+

See also
========

  * extend (Macaulay2Doc) -- extend a module map to a chain map,
    if possible

Ways to use trim:
=================

  * "trim(Ideal)" -- see trim (Macaulay2Doc), -- minimize generators
    and relations
  * "trim(Module)" -- see trim (Macaulay2Doc), -- minimize
    generators and relations
  * "trim(MonomialIdeal)" -- see trim (Macaulay2Doc), -- minimize
    generators and relations
  * "trim(Permutation)"
  * "trim(QuotientRing)" -- see trim (Macaulay2Doc), -- minimize
    generators and relations
  * "trim(Ring)" -- see trim (Macaulay2Doc), -- minimize generators
    and relations

For the programmer
==================

The object trim (Macaulay2Doc), is a method function with options (Macaulay2Doc).

VisibleList _ Permutation -- computes the action of a permutation on a list
***************************************************************************

Synopsis
========

  * Operator: _ (Macaulay2Doc),
  * Usage:
        l_p
  * Inputs:
      * l, a visible list (Macaulay2Doc),
      * w, a permutation,
  * Outputs:
      * a visible list (Macaulay2Doc),

Description
===========

A permutation $p$ acts on the elements of list by permuting the elements of the
list according to the permutation. More precisely, if $L = \{ e_1, \dots, e_k
\}$ is a list and $p=(p_1, \dots, p_n)$ is a permutation, then the action is
given by $p*L = \{ e_{p(1)}, \dots, e_{p(k)}}$.

The permutation cannot permute more than #l elements.

+-------------------------------------+
|i1 : p = permutation {3,1,2,5,4,7,6} |
|                                     |
|o1 = Permutation{3, 1, 2, 5, 4, 7, 6}|
|                                     |
|o1 : Permutation                     |
+-------------------------------------+
|i2 : L = {3,1,2,5,4,6,7}             |
|                                     |
|o2 = {3, 1, 2, 5, 4, 6, 7}           |
|                                     |
|o2 : List                            |
+-------------------------------------+
|i3 : L_p                             |
|                                     |
|o3 = {2, 3, 1, 4, 5, 7, 6}           |
|                                     |
|o3 : List                            |
+-------------------------------------+

The permutation can be a permutation on less than #l elements.

+--------------------------------+
|i4 : p = permutation {3,1,2,4,5}|
|                                |
|o4 = Permutation{3, 1, 2, 4, 5} |
|                                |
|o4 : Permutation                |
+--------------------------------+
|i5 : L = {3,1,2,5,4,6,7}        |
|                                |
|o5 = {3, 1, 2, 5, 4, 6, 7}      |
|                                |
|o5 : List                       |
+--------------------------------+
|i6 : L_p                        |
|                                |
|o6 = {2, 3, 1, 5, 4, 6, 7}      |
|                                |
|o6 : List                       |
+--------------------------------+

See also
========

  * Permutation * VisibleList -- computes
    the action of a permutation on a list

Ways to use this method:
========================

  * VisibleList _ Permutation -- computes
    the action of a permutation on a list

Weak
****

Functions with optional argument named Weak:
============================================

  * exceedances(...,Weak=>...) (missing documentation)

For the programmer
==================

The object Weak (missing documentation) is a symbol (Macaulay2Doc).