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:
|
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$.
|
|
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$.
|
|
|
We can also multiply (or compose) two permutations. We follow the convention of $(p*q)(i) = p(q(i))$.
|
|
|
This also let's us compute powers of permutations.
|
|
|
|
|
|
Group actions.
A permutation on $n$ symbols acts on lists of size $n$ by permuting its contents according to the permutation.
|
|
|
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.
|
|
|
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).
|
|
|
Just as in the case of lists, the size of the matrix can be larger than $n$.
|
|
|
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.
|
|
|
|
|
We can also act on the columns of the matrix in a similar way.
|
|
|
|
|
Cycle decompositions.
Every permutation can be decomposed as a product of disjoint cycles. This can be computed with cycleDecomposition.
|
|
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.
|
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.
|
|
|
An ascending run is a maximal subsequence of successive ascents. Similarly, a descending run is a maximal subsequence of successive descents.
|
|
|
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$.
|
|
A permutation $p$ has a saliance at $i$ if $p(j) < p(i)$ for all $j > i$.
|
|
A permutation $p$ has a record at $i$ if $p(j) < p(i)$ for all $j < i$.
|
|
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$.
|
|
Some patterns are common enough that those pattern-avoiding permutations are given a name, such as vexillary for those that are $2143$-avoiding.
|
|
We can also check if a permutation simultaneously avoids a list of patterns.
|
|
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.
|
|
|
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)$.
|
|
Miscellaneous.
We can compute the inverse of a 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.
|
|
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.
|
|
|
|
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.
|
|
|
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.
|
|