Tutorial: Working with Permutations - Maple Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Permutations : Tutorial: Working with Permutations

Working with Permutations

Creating a Permutation

To create a permutation in Maple, you must specify either an explicit list of the images of the integers in the range 1..n, or the disjoint cycle structure of the permutation. In the first case, you use a list L of the form [a__1, a__2, ..., a__n], where a__i is the image of i under the permutation.

 > p := Perm( [2, 3, 1] );
 ${p}{≔}\left({1}{,}{2}{,}{3}\right)$ (1)

To create a permutation by specifying its disjoint cycle structure, use nested lists in which each sublist represents the corresponding cycle.

 > p := Perm( [[1,3],[2,5,4]] );
 ${p}{≔}\left({1}{,}{3}\right)\left({2}{,}{5}{,}{4}\right)$ (2)

In this earlier example, the sublist [1,3] represents the cycle (transposition) that interchanges the points $1$ and $3$, and the sublist [2,5,4] represents the cycle that takes $2$ to $5$, $5$ to $4$ and $4$ to $2$.

Note that permutations are displayed in disjoint cycle notation.

Permutations have type Perm.

 > type( p, 'Perm' );
 ${\mathrm{true}}$ (3)

Many of the commands available for computing with permutations reside in the GroupTheory package, and the following command can be used to access them.

 > with( GroupTheory ):

The Action of a Permutation

To apply a permutation p to a point i, you use the "indexed" notation p[i].  For example,

 > p := Perm( [[1,2],[3,4,5]] );
 ${p}{≔}\left({1}{,}{2}\right)\left({3}{,}{4}{,}{5}\right)$ (4)
 > p[ 3 ];
 ${4}$ (5)

Note: Despite the notation, permutations act on the 'right'. This is important to understand when multiplying (or composing) permutations.

You can also use the PermApply command to compute the image of a point, or to map a permutation onto a set or list of points.

 > PermApply( p, 3 );
 ${4}$ (6)
 > map2( PermApply, p, [ 1, 3, 5 ] );
 $\left[{2}{,}{4}{,}{3}\right]$ (7)

The set of points that are actually displaced by a permutation is called the "support" of the permutation. To compute the set of moved points, use the PermSupport command.

 > p := Perm( [[1, 3], [4,6,7]] );
 ${p}{≔}\left({1}{,}{3}\right)\left({4}{,}{6}{,}{7}\right)$ (8)
 > PermSupport( p );
 $\left\{{1}{,}{3}{,}{4}{,}{6}{,}{7}\right\}$ (9)

The largest point moved by a permutation is called the "degree" of the permutation, you can compute it by using the PermDegree command.

 > PermDegree( p );
 ${7}$ (10)

The PermFixed command returns the set of those points less or equal to the degree of a permutation that are fixed by it.

 > PermFixed( p );
 $\left\{{2}{,}{5}\right\}$ (11)

Permutation Arithmetic

The noncommutative multiplication operator . is used to multiply (or compose) two permutations.

 > a := Perm( [[1,2]] ); b := Perm( [[2,3,4]] );
 ${a}{≔}\left({1}{,}{2}\right)$
 ${b}{≔}\left({2}{,}{3}{,}{4}\right)$ (12)
 > a . b;
 $\left({1}{,}{3}{,}{4}{,}{2}\right)$ (13)
 > b . a;
 $\left({1}{,}{2}{,}{3}{,}{4}\right)$ (14)

Observe that $a·b$ and $b·a$ are different permutations; that is, multiplication of permutation is, in general, 'not' commutative.

You can compute a power ${a}^{n}$, for an integer $n$, of a permutation $a$, by using the ^ operator.

 > a^37;
 $\left({1}{,}{2}\right)$ (15)
 > b^(-2);
 $\left({2}{,}{3}{,}{4}\right)$ (16)

In particular, you can compute the inverse of a permutation as a power with $-1$.

 > b^(-1);
 $\left({2}{,}{4}{,}{3}\right)$ (17)

You can also compute the inverse of a permutation by using the PermInverse command.

 > PermInverse( b );
 $\left({2}{,}{4}{,}{3}\right)$ (18)

Note that computing powers of a permutation is efficient for large powers.

 > b^(7^(7^7));
 $\left({2}{,}{3}{,}{4}\right)$ (19)

Alternatively, you can use the PermPower command.

 > PermPower( a, 5 );
 $\left({1}{,}{2}\right)$ (20)

The smallest positive integer $n$ for which ${a}^{n}$ is the identity permutation is called the "order" of the permutation $a$.  The PermOrder command computes the order of a permutation.

 > PermOrder( b );
 ${3}$ (21)
 > PermOrder( a );
 ${2}$ (22)

To compute the conjugate ${a}^{b}$ of a permutation $a$ by a permutation $b$, you can use either exponential notation, or the PermConjugate command.

 > a^b;
 $\left({1}{,}{3}\right)$ (23)
 > PermConjugate( a, b );
 $\left({1}{,}{3}\right)$ (24)

The commutator $\frac{1}{a}·\frac{1}{b}·a·b$ of two permutations $a$ and $b$ is computed by the PermCommutator command.

 > PermCommutator( a, b );
 $\left({1}{,}{2}{,}{3}\right)$ (25)

Other Operations on Permutations

 • Every permutation $p$ can be written as a product of transpositions. There are infinitely many such products for any given permutation, but the number of transpositions in such a product is either always even or always odd. The "parity" of $p$ is defined to be $1$ if $p$ can be written as a product of an even number of transpositions, and is defined to be $-1$ otherwise. This defines a homomorphism from the symmetric group ${S}_{n}$ to the multiplicative group $\left\{-1,1\right\}$. The PermParity command computes this homomorphism.
 > PermParity( a );
 ${-1}$ (26)
 > PermParity( b );
 ${1}$ (27)
 • Every permutation can be written, in an essentially unique way, as a product of disjoint cycles. The multi-set of lengths of these cycles is called the "cycle type" of the permutation, and the PermCycleType command computes the cycle type as a list of the form $\left[{c}_{1},{c}_{2},..,{c}_{k}\right]$, where the lengths of the cycles in a disjoint cycle decomposition of the permutation are listed in non-decreasing order. Thus, a cycle type of $\left[2,2,3,5,5\right]$ indicates a permutation that is a product of two transpositions, one $3$-cycle and two $5$-cycles.
 > b;
 $\left({2}{,}{3}{,}{4}\right)$ (28)
 > PermCycleType( b );
 $\left[{3}\right]$ (29)
 > PermCycleType( Perm([[1,2],[3,4,5],[6,7,8],[9,10],[11,12,13,14,15]] ) );
 $\left[{2}{,}{2}{,}{3}{,}{3}{,}{5}\right]$ (30)

Compatibility

 • The Working with Permutations tutorial was introduced in Maple 2015.