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

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.1 of Permutations.

Citation
========

If you have used this package in your research, please cite it as follows:

+-----------------------------------------------------------------------------+
|@misc{PermutationsSource,                                                    |
|  title = {{Permutations: functions for working with permutations. Version   |
|  author = {Sean Grate},                                                     |
|  howpublished = {A \emph{Macaulay2} package available at                    |
|    \url{https://github.com/Macaulay2/M2/tree/master/M2/Macaulay2/packages   |
|}                                                                            |
|-----------------------------------------------------------------------------|
|~1.1}},                                                                      |
|                                                                             |
|                                                                             |
|}}                                                                           |
+-----------------------------------------------------------------------------+

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
      * isSeparable -- whether a permutation is separable.
      * isVexillary -- whether a permutation is vexillary
      * ord -- computes the order of a permutation
      * "permutation" -- see Permutation, -- the Permutation
        type
      * randomPermutation -- generates a random
        permutation
      * records -- computes the saliances of a permutation
      * reducedWords -- computes the reduced words of a
        permutation
      * saliances -- computes the saliances of a permutation
      * strongBruhatOrder -- compares two
        permutations in the (strong) Bruhat order
      * symmetricGroupPoset -- constructs the poset
        of the symmetric group under a partial order
      * transposition -- constructs a transposition
      * weakBruhatOrder -- compares two permutations in
        the weak Bruhat order
  * 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 permutation 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
      * "isSeparable(Permutation)" -- see isSeparable, --
        whether a permutation is separable.
      * "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
      * "randomPermutation(ZZ)" -- see randomPermutation,
        -- generates a random permutation
      * "records(Permutation)" -- see records, -- computes the
        saliances of a permutation
      * "reducedWords(Permutation)" -- see reducedWords, --
        computes the reduced words of a permutation
      * "saliances(Permutation)" -- see saliances, -- computes
        the saliances of a permutation
      * sign(Permutation) -- computes the sign of
        a permutation
      * "strongBruhatOrder(Permutation,Permutation)" -- see
        strongBruhatOrder, -- compares two permutations in
        the (strong) Bruhat order
      * "symmetricGroupPoset(ZZ,Function)" -- see symmetricGroupPoset,
        -- constructs the poset of the symmetric group
        under a partial order
      * tex(Permutation) (missing documentation)
      * toString(Permutation) (missing documentation)
      * "transposition(ZZ)" -- see transposition, --
        constructs a transposition
      * "transposition(ZZ,ZZ)" -- see transposition, --
        constructs a transposition
      * "trim(Permutation)" -- see trim, -- rewrites a permutation
        in its smallest representation
      * VisibleList _ Permutation, --
        computes the action of a permutation on a list
      * "weakBruhatOrder(Permutation,Permutation)" -- see
        weakBruhatOrder, -- compares two permutations in the
        weak Bruhat order
  * Symbols
      * Weak (missing documentation)
      * "Side" -- see weakBruhatOrder, -- compares two
        permutations in the weak Bruhat order

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

The object Permutations, is a package (Macaulay2Doc),
defined in Permutations.m2, with auxiliary files in Permutations/.

-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/packageDocs.m2:12:0.

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:49:0.

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:78:0.

Ascents, descents, runs, exceedances, and records -- a detailed overview of permutations in Macaulay2
*****************************************************************************************************

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.

+---------------------------------+
|i1 : p = permutation {3,1,2,5,4};|
+---------------------------------+
|i2 : ascents p                   |
|                                 |
|o2 = {2, 3}                      |
|                                 |
|o2 : List                        |
+---------------------------------+
|i3 : descents p                  |
|                                 |
|o3 = {1, 4}                      |
|                                 |
|o3 : List                        |
+---------------------------------+

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

+----------------------------------+
|i4 : p = permutation {3,1,2,5,4}; |
+----------------------------------+
|i5 : ascendingRuns p              |
|                                  |
|o5 = {1 : (3), (1, 2, 5), 1 : (4)}|
|                                  |
|o5 : List                         |
+----------------------------------+
|i6 : descendingRuns p             |
|                                  |
|o6 = {(3, 1), 1 : (2), (5, 4)}    |
|                                  |
|o6 : 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$.

+---------------------------------+
|i7 : p = permutation {3,1,2,5,4};|
+---------------------------------+
|i8 : exceedances p               |
|                                 |
|o8 = {1, 4}                      |
|                                 |
|o8 : List                        |
+---------------------------------+

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

+---------------------------------+
|i9 : p = permutation {3,1,2,5,4};|
+---------------------------------+
|i10 : saliances p                |
|                                 |
|o10 = {4, 5}                     |
|                                 |
|o10 : List                       |
+---------------------------------+

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

+----------------------------------+
|i11 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i12 : records p                   |
|                                  |
|o12 = {1, 4}                      |
|                                  |
|o12 : List                        |
+----------------------------------+
-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/packageDocs.m2:247:0.

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

  * 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                      |
+--------------------------------+

Acknowledgement
===============

This method was ported over from the MatrixSchubert (missing documentation)
package.

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.
  * isSeparable -- whether a permutation is separable.
  * isVexillary -- whether a permutation is vexillary

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

  * "avoidsPattern(Permutation,List)"

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

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

-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/patternAvoidanceDocs.m2:32:0.

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

  * 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                                    |
+----------------------------------------------+

Acknowledgement
===============

This method was ported over from the MatrixSchubert (missing documentation)
package.

See also
========

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

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

  * "avoidsPatterns(Permutation,List)"

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

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

-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/patternAvoidanceDocs.m2:62:0.

Basic operations -- an overview of basic operations with permutations
*********************************************************************

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

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

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

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

This also let's us compute powers of permutations.

+--------------------------------+
|i7 : p = permutation {3,1,2,5,4}|
|                                |
|o7 = Permutation{3, 1, 2, 5, 4} |
|                                |
|o7 : Permutation                |
+--------------------------------+
|i8 : p^2                        |
|                                |
|o8 = Permutation{2, 3, 1}       |
|                                |
|o8 : Permutation                |
+--------------------------------+
|i9 : p^6                        |
|                                |
|o9 = Permutation{1}             |
|                                |
|o9 : Permutation                |
+--------------------------------+
|i10 : p^0                       |
|                                |
|o10 = Permutation{1, 2, 3, 4, 5}|
|                                |
|o10 : Permutation               |
+--------------------------------+
|i11 : p^(-1)                    |
|                                |
|o11 = Permutation{2, 3, 1, 5, 4}|
|                                |
|o11 : Permutation               |
+--------------------------------+
|i12 : p^(-2)                    |
|                                |
|o12 = Permutation{3, 1, 2}      |
|                                |
|o12 : Permutation               |
+--------------------------------+
-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/packageDocs.m2:95:0.

Bruhat order -- an overview of the Bruhat order for permutations
****************************************************************

The (strong) Bruhat order is a partial order on the symmetric group
$\mathfrak{S}_n$. See [BB05] for more details on Bruhat order.

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

The (right) weak Bruhat order is a partial order on the symmetric group
$\mathfrak{S}_n$. For two permutations $p$ and $q$, $w \leq_R v$ if and only if
$\ell(w) + \ell(v^{-1} w) = \ell(v)$, where $\ell$ denotes the
length(Permutation), of a permutation and $\leq_R$ is
the right weak Bruhat order.

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

The optional argument Side, can be used to specify which
weak Bruhat order to use. The current options are "left" and "right" (default).

+----------------------------------------+
|i7 : weakBruhatOrder(p, q, Side=>"left")|
|                                        |
|o7 = false                              |
+----------------------------------------+

We can use these orders to construct the poset of $\mathfrak{S}_n$ using the
Posets, package. The symmetricGroupPoset,
method constructs the poset of $\mathfrak{S}_n$ with the
Bruhat order for convenience.

+--------------------------------------------------+
|i8 : P = symmetricGroupPoset(4, strongBruhatOrder)|
|                                                  |
|o8 = P                                            |
|                                                  |
|o8 : Poset                                        |
+--------------------------------------------------+
|i9 : Q = symmetricGroupPoset(4, weakBruhatOrder)  |
|                                                  |
|o9 = Q                                            |
|                                                  |
|o9 : Poset                                        |
+--------------------------------------------------+

This allows us to verify, for example, that the weak Bruhat order is
rank-symmetric and Sperner [GG20].

+-----------------------------------------------------------------------------+
|i10 : rankPoly = rankGeneratingFunction Q                                    |
|                                                                             |
|       6     5     4     3     2                                             |
|o10 = q  + 3q  + 5q  + 6q  + 5q  + 3q + 1                                    |
|                                                                             |
|o10 : ZZ[q]                                                                  |
+-----------------------------------------------------------------------------+
|i11 : coeffs = apply(flatten entries (coefficients rankPoly)#1, k -> sub(k,  |
|                                                                             |
|o11 = {1, 3, 5, 6, 5, 3, 1}                                                  |
|                                                                             |
|o11 : List                                                                   |
|-----------------------------------------------------------------------------|
|ZZ))                                                                         |
+-----------------------------------------------------------------------------+
|i12 : d = (degree rankPoly)#0                                                |
|                                                                             |
|o12 = 6                                                                      |
+-----------------------------------------------------------------------------+
|i13 : all(apply(#coeffs // 2, i -> coeffs#i == coeffs#(d-i)))                |
|                                                                             |
|o13 = true                                                                   |
+-----------------------------------------------------------------------------+
|i14 : isSperner P                                                            |
|                                                                             |
|o14 = true                                                                   |
+-----------------------------------------------------------------------------+

References
==========

  * [BB05] Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups
    (see https://link.springer.com/book/10.1007/3-540-27596-7 ), Graduate Texts
    in Mathematics, 231, Springer, New York, 2005
  * [GG20] Christian Gaetz and Yibo Gao, The weak Bruhat order on the symmetric
    group is Sperner, Sém. Lothar. Combin. 82B (2020), Art. 35, 8 pp.
-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/packageDocs.m2:344:0.

Creating permutations -- an overview of 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(Permutation), 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.

-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/packageDocs.m2:63:0.

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:106:0.

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:130:0.

Cyclic decomposition -- an overview of cyclic decompositions of permutations
****************************************************************************

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

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

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.

+----------------+
|i3 : cycleType p|
|                |
|o3 = (3, 2)     |
|                |
|o3 : Sequence   |
+----------------+

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

+---------------------------------+
|i4 : p = permutation {3,1,2,5,4};|
+---------------------------------+
|i5 : foataBijection p            |
|                                 |
|o5 = Permutation{3, 2, 1, 5, 4}  |
|                                 |
|o5 : Permutation                 |
+---------------------------------+

Decomposition into transpositions
=================================

A permutation can also be decomposed as a product of transpositions. When this
is done minimally (with respect to the number of transpositions used), such
decompositions are called reduced words. We can compute these with
reducedWords.

+--------------------------------------+
|i6 : p = permutation {3,1,2,5,4};     |
+--------------------------------------+
|i7 : reducedWords p                   |
|                                      |
|o7 = {{1, 2, 4}, {1, 4, 2}, {4, 1, 2}}|
|                                      |
|o7 : List                             |
+--------------------------------------+

We can verify that these reduced words multiply to the original permutation.

+-----------------------------------------------------------------------------+
|i8 : all(reducedWords p, word -> product reverse apply(word, transposition)  |
|                                                                             |
|o8 = true                                                                    |
|-----------------------------------------------------------------------------|
|== p)                                                                        |
+-----------------------------------------------------------------------------+
-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/packageDocs.m2:204:0.

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:158:0.

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:187:0.

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

  * Usage:
        exceedances w
        exceedances(w, Weak)
  * Inputs:
      * w, a permutation,
  * Optional inputs (Macaulay2Doc),:
      * Weak => ..., 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).

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:224:0.

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

  * Usage:
        extend(w,n)
  * Inputs:
      * w, a permutation,
      * n, an integer (Macaulay2Doc),
  * Optional inputs (Macaulay2Doc),:
      * Verify (missing documentation) => ..., 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(Complex,Complex,Matrix)" -- see
    extend(Complex,Complex,Matrix,Sequence) (Complexes),
    -- extend a
    map of modules to a map of chain complexes
  * extend(Complex,Complex,Matrix,Sequence) (Complexes)
    -- extend a
    map of modules to a map of chain complexes
  * 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).

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:250:0.

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

  * Function: extend (Macaulay2Doc),
  * Usage:
        e = extend(w,v)
  * Inputs:
      * w, a permutation,
      * v, a permutation,
  * Optional inputs (Macaulay2Doc),:
      * Verify (missing documentation) => ..., 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
    permutation 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
-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:280:0.

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:304:0.

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:329:0.

Group actions -- an overview of permutations acting on objects in Macaulay2
***************************************************************************

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

+---------------------------------+
|i1 : p = permutation {3,1,2,5,4};|
+---------------------------------+
|i2 : L = {1,2,3,4,5};            |
+---------------------------------+
|i3 : p*L                         |
|                                 |
|o3 = {3, 1, 2, 5, 4}             |
|                                 |
|o3 : 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.

+---------------------------------+
|i4 : p = permutation {3,1,2,5,4};|
+---------------------------------+
|i5 : L = {1,2,3,4,5,6,7,8};      |
+---------------------------------+
|i6 : p*L                         |
|                                 |
|o6 = {3, 1, 2, 5, 4, 6, 7, 8}    |
|                                 |
|o6 : 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).

+-----------------------------+
|i7 : p = permutation {3,1,2};|
+-----------------------------+
|i8 : M = id_(ZZ^3);          |
|                             |
|              3       3      |
|o8 : Matrix ZZ  <-- ZZ       |
+-----------------------------+
|i9 : p*M                     |
|                             |
|o9 = | 0 1 0 |               |
|     | 0 0 1 |               |
|     | 1 0 0 |               |
|                             |
|              3       3      |
|o9 : Matrix ZZ  <-- ZZ       |
+-----------------------------+

Just as in the case of lists, the size of the matrix can be larger than $n$.
Example p = permutation {3,1,2}; M = id_(ZZ^5); p*M

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.

+-------------------------------------+
|i10 : p = permutation {3,1,2};       |
+-------------------------------------+
|i11 : M = id_(ZZ^3) || id_(ZZ^3);    |
|                                     |
|               6       3             |
|o11 : Matrix ZZ  <-- ZZ              |
+-------------------------------------+
|i12 : N = matrix {{1,0},{0,1},{1,1}};|
|                                     |
|               3       2             |
|o12 : Matrix ZZ  <-- ZZ              |
+-------------------------------------+
|i13 : p*M                            |
|                                     |
|o13 = | 0 1 0 |                      |
|      | 0 0 1 |                      |
|      | 1 0 0 |                      |
|      | 1 0 0 |                      |
|      | 0 1 0 |                      |
|      | 0 0 1 |                      |
|                                     |
|               6       3             |
|o13 : Matrix ZZ  <-- ZZ              |
+-------------------------------------+
|i14 : p*N                            |
|                                     |
|o14 = | 0 1 |                        |
|      | 1 1 |                        |
|      | 1 0 |                        |
|                                     |
|               3       2             |
|o14 : Matrix ZZ  <-- ZZ              |
+-------------------------------------+

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

+-------------------------------------------------+
|i15 : p = permutation {3,1,2};                   |
+-------------------------------------------------+
|i16 : M = id_(ZZ^3) || id_(ZZ^3);                |
|                                                 |
|               6       3                         |
|o16 : Matrix ZZ  <-- ZZ                          |
+-------------------------------------------------+
|i17 : N = matrix {{1,0,0,0},{0,1,0,0},{0,0,1,0}};|
|                                                 |
|               3       4                         |
|o17 : Matrix ZZ  <-- ZZ                          |
+-------------------------------------------------+
|i18 : M*p                                        |
|                                                 |
|o18 = | 0 0 1 |                                  |
|      | 1 0 0 |                                  |
|      | 0 1 0 |                                  |
|      | 0 0 1 |                                  |
|      | 1 0 0 |                                  |
|      | 0 1 0 |                                  |
|                                                 |
|               6       3                         |
|o18 : Matrix ZZ  <-- ZZ                          |
+-------------------------------------------------+
|i19 : N*p                                        |
|                                                 |
|o19 = | 0 0 1 0 |                                |
|      | 1 0 0 0 |                                |
|      | 0 1 0 0 |                                |
|                                                 |
|               3       4                         |
|o19 : Matrix ZZ  <-- ZZ                          |
+-------------------------------------------------+
-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/packageDocs.m2:153:0.

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

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

The source of this document is in Permutations/Documentation/mainDocs.m2:347:0.

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:371:0.

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

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

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

A permutation $p$ is Cartwright-Sturmfels if it avoids all of the following
patterns: $12543$, $13254$, $13524$, $13542$, $21543$, $125364$, $125634$,
$215364$, $215634$, $315264$, $315624$, and $315642$.

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

Acknowledgement
===============

This method was ported over from the MatrixSchubert (missing documentation)
package.

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.
  * isSeparable -- whether a permutation is separable.
  * isVexillary -- whether a permutation is vexillary

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

  * "isCartwrightSturmfels(Permutation)"

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

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

-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/patternAvoidanceDocs.m2:93:0.

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

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

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

A permutation $p$ is Conca-De Negri-Gorla (CDG) if it avoids all of the
following patterns: $13254$, $21543$, $214635$, $215364$, $215634$, $241635$,
$315264$, and $4261735$.

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

Acknowledgement
===============

This method was ported over from the MatrixSchubert (missing documentation)
package.

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
  * isSeparable -- whether a permutation is separable.
  * isVexillary -- whether a permutation is vexillary

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

  * "isCDG(Permutation)"

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

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

-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/patternAvoidanceDocs.m2:124:0.

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:394:0.

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

  * 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 (Macaulay2Doc),
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(Permutation) -- computes the sign of a
    permutation

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

  * "isEven(Permutation)"

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:420:0.

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

  * 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 (Macaulay2Doc),
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(Permutation) -- computes the sign of a
    permutation

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

  * "isOdd(Permutation)"

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:446:0.

isSeparable -- whether a permutation is separable.
**************************************************

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

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

A permutation $p$ is separable if it avoids $2413$ and $3142$.

+-------------------------------------------+
|i1 : p = permutation {1,4,3,2,5,9,7,8,6}   |
|                                           |
|o1 = Permutation{1, 4, 3, 2, 5, 9, 7, 8, 6}|
|                                           |
|o1 : Permutation                           |
+-------------------------------------------+
|i2 : isSeparable 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
  * isCDG -- whether a permutation is CDG.
  * isVexillary -- whether a permutation is vexillary

Ways to use isSeparable:
========================

  * "isSeparable(Permutation)"

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

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

-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/patternAvoidanceDocs.m2:151:0.

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

  * 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                      |
+--------------------------------+

Acknowledgement
===============

This method was ported over from the MatrixSchubert (missing documentation)
package.

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.
  * isSeparable -- whether a permutation is separable.

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

  * "isVexillary(Permutation)"

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

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

-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/patternAvoidanceDocs.m2:179:0.

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

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

The source of this document is in Permutations/Documentation/mainDocs.m2:471:0.

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

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

The source of this document is in Permutations/Documentation/mainDocs.m2:493:0.

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

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

The source of this document is in
Permutations/Documentation/operationsDocs.m2:277:0.

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

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

The source of this document is in
Permutations/Documentation/operationsDocs.m2:310:0.

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

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

The source of this document is in
Permutations/Documentation/operationsDocs.m2:244:0.

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

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

The source of this document is in Permutations/Documentation/mainDocs.m2:518:0.

Miscellaneous -- a detailed overview of permutations in Macaulay2
*****************************************************************

We can compute the inverse of a permutation.

+---------------------------------+
|i1 : p = permutation {3,1,2,5,4};|
+---------------------------------+
|i2 : inverse p                   |
|                                 |
|o2 = Permutation{2, 3, 1, 5, 4}  |
|                                 |
|o2 : 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.

+---------------------------------+
|i3 : p = permutation {3,1,2,5,4};|
+---------------------------------+
|i4 : ord p                       |
|                                 |
|o4 = 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.

+---------------------------------+
|i5 : p = permutation {3,1,2,5,4};|
+---------------------------------+
|i6 : sign p                      |
|                                 |
|o6 = -1                          |
+---------------------------------+
|i7 : isEven p                    |
|                                 |
|o7 = false                       |
+---------------------------------+
|i8 : isOdd p                     |
|                                 |
|o8 = 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.

+---------------------------------+
|i9 : p = permutation {3,1,2,5,4};|
+---------------------------------+
|i10 : isDerangement p            |
|                                 |
|o10 = true                       |
+---------------------------------+
|i11 : fixedPoints p              |
|                                 |
|o11 = {}                         |
|                                 |
|o11 : 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.

+----------------------------------+
|i12 : p = permutation {3,1,2,5,4};|
+----------------------------------+
|i13 : inversions p                |
|                                  |
|o13 = {{1, 2}, {1, 3}, {4, 5}}    |
|                                  |
|o13 : List                        |
+----------------------------------+
-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/packageDocs.m2:386:0.

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:541:0.

Pattern avoidance -- an overview of pattern avoidance for permutations in Macaulay2
***********************************************************************************

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

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

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

+---------------------------------+
|i3 : p = permutation {3,1,2,5,4};|
+---------------------------------+
|i4 : isVexillary p               |
|                                 |
|o4 = false                       |
+---------------------------------+

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

+---------------------------------------------+
|i5 : p = permutation {3,1,2,5,4};            |
+---------------------------------------------+
|i6 : avoidsPatterns(p, {{2,1,4,3},{1,4,3,2}})|
|                                             |
|o6 = false                                   |
+---------------------------------------------+

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

+---------------------------------+
|i7 : p = permutation {3,1,2,5,4};|
+---------------------------------+
|i8 : isCartwrightSturmfels p     |
|                                 |
|o8 = true                        |
+---------------------------------+
|i9 : isCDG p                     |
|                                 |
|o9 = true                        |
+---------------------------------+
-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/packageDocs.m2:282:0.

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 permutation 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
  * "randomPermutation(ZZ)" -- see randomPermutation,
    -- generates a random permutation
  * "transposition(ZZ)" -- see transposition, --
    constructs a transposition
  * "transposition(ZZ,ZZ)" -- see transposition, --
    constructs a transposition
  * "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
  * "isSeparable(Permutation)" -- see isSeparable, --
    whether a permutation is separable.
  * "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
  * "reducedWords(Permutation)" -- see reducedWords, --
    computes the reduced words of a permutation
  * "saliances(Permutation)" -- see saliances, -- computes the
    saliances of a permutation
  * sign(Permutation) -- computes the sign of a
    permutation
  * "strongBruhatOrder(Permutation,Permutation)" -- see
    strongBruhatOrder, -- compares two permutations in the
    (strong) Bruhat order
  * tex(Permutation) (missing documentation)
  * toString(Permutation) (missing documentation)
  * VisibleList _ Permutation -- computes
    the action of a permutation on a list
  * "weakBruhatOrder(Permutation,Permutation)" -- see weakBruhatOrder,
    -- compares two permutations in the weak Bruhat order

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:21:0.

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

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

The source of this document is in
Permutations/Documentation/operationsDocs.m2:211:0.

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

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

The source of this document is in
Permutations/Documentation/operationsDocs.m2:339:0.

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

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

The source of this document is in
Permutations/Documentation/operationsDocs.m2:143:0.

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

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

The source of this document is in
Permutations/Documentation/operationsDocs.m2:108:0.

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

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

The source of this document is in
Permutations/Documentation/operationsDocs.m2:361:0.

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

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

The source of this document is in
Permutations/Documentation/operationsDocs.m2:52:0.

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

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

The source of this document is in
Permutations/Documentation/operationsDocs.m2:80:0.

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

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

The source of this document is in
Permutations/Documentation/operationsDocs.m2:24:0.

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:

  0. Creating permutations, -- an overview of
     creating permutations
  1. Basic operations, -- an overview of basic
     operations with permutations
  2. Group actions, -- an overview of permutations acting
     on objects in Macaulay2
  3. Cyclic decomposition, -- an overview of cyclic
     decompositions of permutations
  4. Ascents, descents, runs, exceedances, and records,
     -- a detailed overview of
     permutations in Macaulay2
  5. Pattern avoidance, -- an overview of pattern
     avoidance for permutations in Macaulay2
  6. Bruhat order, -- an overview of the Bruhat order for
     permutations
  7. Miscellaneous, -- a detailed overview of permutations
     in Macaulay2
-------------------------------------------------------------------------------

The source of this document is in
Permutations/Documentation/packageDocs.m2:36:0.

randomPermutation -- generates a random permutation
***************************************************

  * Usage:
        randomPermutation n
  * Inputs:
      * n, an integer (Macaulay2Doc),
  * Outputs:
      * a permutation,

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

Generates a random permutation on $1..n$.

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

Ways to use randomPermutation:
==============================

  * "randomPermutation(ZZ)"

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:561:0.

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:589:0.

reducedWords -- computes the reduced words of a permutation
***********************************************************

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

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

A permutation $p$ can be expressed as a product of transpositions. A reduced
word is a minimal-length expression of a permutation as a product of
transpositions. The reducedWords method computes all of the reduced words of a
permutation. A word is represented by a list of integers, where $i$ denotes the
transposition $(i,i+1)$.

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

We can check that a reduced word multiplies out to the original permutation.
Note that we need to multiply from right to left, so we must reverse the list.

+------------------------------------------------------+
|i3 : word = words#0                                   |
|                                                      |
|o3 = {1, 2, 1, 3, 2, 1}                               |
|                                                      |
|o3 : List                                             |
+------------------------------------------------------+
|i4 : product reverse apply(word, i -> transposition i)|
|                                                      |
|o4 = Permutation{4, 3, 2, 1}                          |
|                                                      |
|o4 : Permutation                                      |
+------------------------------------------------------+

See also
========

  * length (Macaulay2Doc) -- length of an object
  * transposition -- constructs a transposition

Ways to use reducedWords:
=========================

  * "reducedWords(Permutation)"

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:624:0.

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:652:0.

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

  * Function: sign (Macaulay2Doc),
  * 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 this method:
========================

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

The source of this document is in Permutations/Documentation/mainDocs.m2:679:0.

strongBruhatOrder -- compares two permutations in the (strong) Bruhat order
***************************************************************************

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

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

The (strong) Bruhat order is a partial order on the symmetric group
$\mathfrak{S}_n$. See [BB05] for more details on the strong Bruhat order.

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

References
==========

  * [BB05] Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups
    (see https://link.springer.com/book/10.1007/3-540-27596-7 ), Graduate Texts
    in Mathematics, 231, Springer, New York, 2005

See also
========

  * weakBruhatOrder -- compares two permutations in the
    weak Bruhat order
  * symmetricGroupPoset -- constructs the poset of
    the symmetric group under a partial order

Ways to use strongBruhatOrder:
==============================

  * "strongBruhatOrder(Permutation,Permutation)"

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:714:0.

symmetricGroupPoset -- constructs the poset of the symmetric group under a partial order
****************************************************************************************

  * Usage:
        symmetricGroupPoset(n,f)
  * Inputs:
      * w, a permutation,
      * f, a function (Macaulay2Doc),
  * Outputs:
      * a Boolean value (Macaulay2Doc),

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

Using the Posets, package, we can construct the poset on the
symmetric group $\mathfrak{S}_n$ under a partial order. See [BB05] for more
details on Bruhat order.

+-------------------------------------------------------------------------+
|i1 : symmetricGroupPoset(4, strongBruhatOrder)                           |
|                                                                         |
|o1 = Relation Matrix: | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ||
|                      | 0 1 0 1 1 1 0 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 ||
|                      | 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ||
|                      | 0 0 0 1 0 1 0 0 0 1 0 1 0 1 0 1 1 1 0 1 0 1 1 1 ||
|                      | 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 ||
|                      | 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 1 1 ||
|                      | 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ||
|                      | 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 ||
|                      | 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 ||
|                                                                         |
|o1 : Poset                                                               |
+-------------------------------------------------------------------------+

With a little bit of finagling, we can also construct the poset using the
non-default left weak Bruhat order.

+-------------------------------------------------------------------------+
|i2 : partialOrder = (w,v) -> weakBruhatOrder(w,v, Side=>"left")          |
|                                                                         |
|o2 = partialOrder                                                        |
|                                                                         |
|o2 : FunctionClosure                                                     |
+-------------------------------------------------------------------------+
|i3 : symmetricGroupPoset(4, partialOrder)                                |
|                                                                         |
|o3 = Relation Matrix: | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ||
|                      | 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 ||
|                      | 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1 ||
|                      | 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 ||
|                      | 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 ||
|                      | 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 ||
|                      | 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 ||
|                      | 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 ||
|                      | 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 ||
|                      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 ||
|                                                                         |
|o3 : Poset                                                               |
+-------------------------------------------------------------------------+

See also
========

  * weakBruhatOrder -- compares two permutations in the
    weak Bruhat order
  * strongBruhatOrder -- compares two permutations in
    the (strong) Bruhat order

Ways to use symmetricGroupPoset:
================================

  * "symmetricGroupPoset(ZZ,Function)"

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:746:0.

transposition -- constructs a transposition
*******************************************

  * Usage:
        transposition i
  * Inputs:
      * i, an integer (Macaulay2Doc),
      * j, an integer (Macaulay2Doc),
  * Outputs:
      * a permutation,

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

This method constructs the transposition $(i,i+1)$.

+----------------------------+
|i1 : transposition 3        |
|                            |
|o1 = Permutation{1, 2, 4, 3}|
|                            |
|o1 : Permutation            |
+----------------------------+

When two arguments are passed, this constructs the transposition $(i,j)$.

+-------------------------------+
|i2 : transposition(3,5)        |
|                               |
|o2 = Permutation{1, 2, 5, 4, 3}|
|                               |
|o2 : Permutation               |
+-------------------------------+

Ways to use transposition:
==========================

  * "transposition(ZZ)"
  * "transposition(ZZ,ZZ)"

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:771:0.

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

  * 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 an object

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:797:0.

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

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

The source of this document is in
Permutations/Documentation/operationsDocs.m2:178:0.

Weak
****

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

  * "exceedances(...,Weak=>...)" -- see exceedances, --
    computes the exceedances of a permutation

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

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

-------------------------------------------------------------------------------

The source of this document is in
/home/runner/work/M2/M2/M2/BUILD/build/Macaulay2/packages/currentString:2:0.

weakBruhatOrder -- compares two permutations in the weak Bruhat order
*********************************************************************

  * Usage:
        weakBruhatOrder(w,v)
  * Inputs:
      * w, a permutation,
      * v, a permutation,
      * Side, a string (Macaulay2Doc), an optional argument to
        specify the side of the Bruhat order
  * Optional inputs (Macaulay2Doc),:
      * Side => ..., default value "right"
  * Outputs:
      * a Boolean value (Macaulay2Doc),

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

The (right) weak Bruhat order is a partial order on the symmetric group
$\mathfrak{S}_n$. For two permutations $p$ and $q$, $w \leq_R v$ if and only if
$\ell(w) + \ell(v^{-1} w) = \ell(v)$, where $\ell$ denotes the
length(Permutation), of a permutation and $\leq_R$ is
the right weak Bruhat order. See [BB05] for more details on the weak Bruhat
order.

+----------------------------+
|i1 : p = permutation {1,3,2}|
|                            |
|o1 = Permutation{1, 3, 2}   |
|                            |
|o1 : Permutation            |
+----------------------------+
|i2 : q = permutation {2,1,3}|
|                            |
|o2 = Permutation{2, 1, 3}   |
|                            |
|o2 : Permutation            |
+----------------------------+
|i3 : r = permutation {3,1,2}|
|                            |
|o3 = Permutation{3, 1, 2}   |
|                            |
|o3 : Permutation            |
+----------------------------+
|i4 : weakBruhatOrder(p, r)  |
|                            |
|o4 = true                   |
+----------------------------+
|i5 : weakBruhatOrder(q, r)  |
|                            |
|o5 = false                  |
+----------------------------+

By default, weakBruhatOrder computes the right weak Bruhat order, but the
optional argument {tt Side} can be used to compute, for example, the left weak
Bruhat order. The current options for Side are "left" and "right".

+--------------------------------------------------------+
|i6 : p = permutation {1,3,2}                            |
|                                                        |
|o6 = Permutation{1, 3, 2}                               |
|                                                        |
|o6 : Permutation                                        |
+--------------------------------------------------------+
|i7 : r = permutation {3,1,2}                            |
|                                                        |
|o7 = Permutation{3, 1, 2}                               |
|                                                        |
|o7 : Permutation                                        |
+--------------------------------------------------------+
|i8 : weakBruhatOrder(inverse p, inverse r, Side=>"left")|
|                                                        |
|o8 = true                                               |
+--------------------------------------------------------+

References
==========

  * [BB05] Anders Björner and Francesco Brenti, Combinatorics of Coxeter groups
    (see https://link.springer.com/book/10.1007/3-540-27596-7 ), Graduate Texts
    in Mathematics, 231, Springer, New York, 2005

See also
========

  * length(Permutation) -- computes the length
    of a permutation
  * strongBruhatOrder -- compares two permutations in
    the (strong) Bruhat order
  * symmetricGroupPoset -- constructs the poset of
    the symmetric group under a partial order

Ways to use weakBruhatOrder:
============================

  * "weakBruhatOrder(Permutation,Permutation)"

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

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

-------------------------------------------------------------------------------

The source of this document is in Permutations/Documentation/mainDocs.m2:850:0.