Macaulay2 » Documentation
Packages » Permutations :: Permutations Guide
next | previous | forward | backward | up | index | toc

Permutations Guide -- a detailed overview of permutations in Macaulay2

This page gives an overview of the use of permutations.

The sections of the overview are, in order:

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

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

Creating permutations.

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

i1 : p = permutation {3,1,2,4,5}

o1 = Permutation{3, 1, 2, 4, 5}

o1 : Permutation

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

i2 : p = permutation {3,1,2,4,5}

o2 = Permutation{3, 1, 2, 4, 5}

o2 : Permutation
i3 : matrix p

o3 = | 0 1 0 0 0 |
     | 0 0 1 0 0 |
     | 1 0 0 0 0 |
     | 0 0 0 1 0 |
     | 0 0 0 0 1 |

              5       5
o3 : Matrix ZZ  <-- ZZ

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

Basic operations.

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

i4 : p = permutation {3,1,2}

o4 = Permutation{3, 1, 2}

o4 : Permutation
i5 : q = permutation {3,1,2,4,5}

o5 = Permutation{3, 1, 2, 4, 5}

o5 : Permutation
i6 : p == q

o6 = true

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

i7 : p = permutation {3,1,2,5,4}

o7 = Permutation{3, 1, 2, 5, 4}

o7 : Permutation
i8 : q = permutation {2,1,3,4,5}

o8 = Permutation{2, 1, 3, 4, 5}

o8 : Permutation
i9 : p*q

o9 = Permutation{1, 3, 2, 5, 4}

o9 : Permutation

This also let's us compute powers of permutations.

i10 : p = permutation {3,1,2,5,4}

o10 = Permutation{3, 1, 2, 5, 4}

o10 : Permutation
i11 : p^2

o11 = Permutation{2, 3, 1}

o11 : Permutation
i12 : p^6

o12 = Permutation{1}

o12 : Permutation
i13 : p^0

o13 = Permutation{1, 2, 3, 4, 5}

o13 : Permutation
i14 : p^(-1)

o14 = Permutation{2, 3, 1, 5, 4}

o14 : Permutation
i15 : p^(-2)

o15 = Permutation{3, 1, 2}

o15 : Permutation

Group actions.

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

i16 : p = permutation {3,1,2,5,4};
i17 : L = {1,2,3,4,5};
i18 : p*L

o18 = {3, 1, 2, 5, 4}

o18 : List

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

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

o21 = {3, 1, 2, 5, 4, 6, 7, 8}

o21 : List

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

i22 : p = permutation {3,1,2};
i23 : M = id_(ZZ^3);

               3       3
o23 : Matrix ZZ  <-- ZZ
i24 : p*M

o24 = | 0 1 0 |
      | 0 0 1 |
      | 1 0 0 |

               3       3
o24 : Matrix ZZ  <-- ZZ

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

i25 : p = permutation {3,1,2};
i26 : M = id_(ZZ^5);

               5       5
o26 : Matrix ZZ  <-- ZZ
i27 : p*M

o27 = | 0 1 0 0 0 |
      | 0 0 1 0 0 |
      | 1 0 0 0 0 |
      | 0 0 0 1 0 |
      | 0 0 0 0 1 |

               5       5
o27 : Matrix ZZ  <-- ZZ

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

i28 : p = permutation {3,1,2};
i29 : M = id_(ZZ^3) || id_(ZZ^3);

               6       3
o29 : Matrix ZZ  <-- ZZ
i30 : N = matrix {{1,0},{0,1},{1,1}};

               3       2
o30 : Matrix ZZ  <-- ZZ
i31 : p*M

o31 = | 0 1 0 |
      | 0 0 1 |
      | 1 0 0 |
      | 1 0 0 |
      | 0 1 0 |
      | 0 0 1 |

               6       3
o31 : Matrix ZZ  <-- ZZ
i32 : p*N

o32 = | 0 1 |
      | 1 1 |
      | 1 0 |

               3       2
o32 : Matrix ZZ  <-- ZZ

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

i33 : p = permutation {3,1,2};
i34 : M = id_(ZZ^3) || id_(ZZ^3);

               6       3
o34 : Matrix ZZ  <-- ZZ
i35 : N = matrix {{1,0,0,0},{0,1,0,0},{0,0,1,0}};

               3       4
o35 : Matrix ZZ  <-- ZZ
i36 : M*p

o36 = | 0 0 1 |
      | 1 0 0 |
      | 0 1 0 |
      | 0 0 1 |
      | 1 0 0 |
      | 0 1 0 |

               6       3
o36 : Matrix ZZ  <-- ZZ
i37 : N*p

o37 = | 0 0 1 0 |
      | 1 0 0 0 |
      | 0 1 0 0 |

               3       4
o37 : Matrix ZZ  <-- ZZ

Cycle decompositions.

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

i38 : p = permutation {3,1,2,5,4}

o38 = Permutation{3, 1, 2, 5, 4}

o38 : Permutation
i39 : cycleDecomposition p

o39 = {(3, 2, 1), (5, 4)}

o39 : List

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

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

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

i40 : cycleType p

o40 = (3, 2)

o40 : Sequence

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

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

i41 : p = permutation {3,1,2,5,4};
i42 : ascents p

o42 = {2, 3}

o42 : List
i43 : descents p

o43 = {1, 4}

o43 : List

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

i44 : p = permutation {3,1,2,5,4};
i45 : ascendingRuns p

o45 = {1 : (3), (1, 2, 5), 1 : (4)}

o45 : List
i46 : descendingRuns p

o46 = {(3, 1), 1 : (2), (5, 4)}

o46 : List

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

i47 : p = permutation {3,1,2,5,4};
i48 : exceedances p

o48 = {1, 4}

o48 : List

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

i49 : p = permutation {3,1,2,5,4};
i50 : saliances p

o50 = {4, 5}

o50 : List

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

i51 : p = permutation {3,1,2,5,4};
i52 : records p

o52 = {1, 4}

o52 : List

Pattern avoidance.

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

i53 : p = permutation {3,1,2,5,4};
i54 : avoidsPattern(p, {2,1,4,3})

o54 = false

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

i55 : p = permutation {3,1,2,5,4};
i56 : isVexillary p

o56 = false

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

i57 : p = permutation {3,1,2,5,4};
i58 : avoidsPatterns(p, {{2,1,4,3},{1,4,3,2}})

o58 = false

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

i59 : p = permutation {3,1,2,5,4};
i60 : isCartwrightSturmfels p

o60 = true
i61 : isCDG p

o61 = true

Foata's fundamental bijection.

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

i62 : p = permutation {3,1,2,5,4};
i63 : foataBijection p

o63 = Permutation{3, 2, 1, 5, 4}

o63 : Permutation

Miscellaneous.

We can compute the inverse of a permutation.

i64 : p = permutation {3,1,2,5,4};
i65 : inverse p

o65 = Permutation{2, 3, 1, 5, 4}

o65 : Permutation

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

i66 : p = permutation {3,1,2,5,4};
i67 : ord p

o67 = 6

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

i68 : p = permutation {3,1,2,5,4};
i69 : sign p

o69 = -1
i70 : isEven p

o70 = false
i71 : isOdd p

o71 = true

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

i72 : p = permutation {3,1,2,5,4};
i73 : isDerangement p

o73 = true
i74 : fixedPoints p

o74 = {}

o74 : List

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

i75 : p = permutation {3,1,2,5,4};
i76 : inversions p

o76 = {{1, 2}, {1, 3}, {4, 5}}

o76 : List

See also