Permutations, the arrangement of objects in a specific order, are a fundamental concept in mathematics and computer science with vast applications in various fields. In principle, they are easy to grasp but hard to handle. Producing and handling permutations can be tedious. But fortunately, we have the SymPy package in Python to help us.

Permutation notations

Permutation notation is a mathematical notation used to describe a permutation, which is a rearrangement of a set of objects. In permutation notation, a permutation of a set of n objects is represented as a sequence of n numbers, where each number represents the position of the corresponding object in the rearranged sequence. Basically, there are two different notations for permutations: cycle notation and array notation.

For example, suppose we have a set of three ordered objects a, b, c. A permutation of this set might be b, c, a, which represents a rearrangement where the second object is moved to the first position, the third object is moved to the second position, and the first object is moved to the third position. We can represent this permutation using permutation notation as (2 3 1), where the numbers in parentheses represent the positions of the objects in the new sequence. This notation is called cycle notation.

More generally, a permutation of a set of n objects can be represented using cycle notation as an n-tuple ( a₁, a₂, …, aₙ ), where each aᵢ is a unique integer between 1 and n representing the position of the ith object in the new sequence.

You can append several cylces. For example, (1 3 5)(2 4) maps 1 to 3, 3 to 5, 5 to 1 (the first cycle), 2 to 4, and 4 to 2 (the second cycle).

There are several ways to define permutations mathematically, but one common definition is that a permutation is a bijection (a one-to-one and onto function) from a set to itself. That is, a permutation is a function that maps each element of the set to a unique element of the set, such that every element of the set is mapped to exactly once. This way of seeing a permutation is nicely represented by the array notation and/or 2-line form.

In array notation, a permutation is written as a row of numbers enclosed in square brackets. Each number in the row represents the image of the corresponding element under the permutation. For example, the permutation (1 3 5)(2 4) can be written in array notation as [3 4 5 2 1]. This means that the first element is mapped to the third element, the second element is mapped to the fourth element, the third element is mapped to the fifth element, the fourth element is mapped to the second element, and the fifth element is mapped to the first element.

In 2-line form, a permutation is written as two rows of numbers separated by a horizontal line. The top row contains the original elements in their original order, and the bottom row contains their images under the permutation. For example, the permutation (1 3 5)(2 4) can be written in 2-line form as:

This means that the first element is mapped to the third element, the second element is mapped to the fourth element, the third element is mapped to the fifth element, the fourth element is mapped to the second element, and the fifth element is mapped to the first element.

Both array notation and 2-line form have their advantages and disadvantages. Array notation is more compact and easier to write for small permutations, but can become cumbersome for larger permutations. 2-line form is more intuitive for visualizing the action of the permutation on the elements, but takes up more space and can be difficult to read for very large permutations.

Defining permutations in sympy

Permutations can be defined in Python both using array notation and cycle notation. Let’s see how to do the permutation of the previous section and start with array notation. The first line of the 2-line form is always the same, so it is redundant. It suffices to specify the second row.

Caveat

Sympy, like always in Python, uses 0-based indexing, which means that the first element is 0 and the last element is 4. Note that the permutation is defined by the list of integers [2, 3, 4, 1, 0], which represents the images of the elements under the permutation. In this case, the permutation maps 1 to 3, 2 to 4, 3 to 5, 4 to 2, and 5 to 1.

from sympy.combinatorics import Permutation
from sympy import init_printing
init_printing(perm_cyclic=False, pretty_print=False)


p = Permutation([2, 3, 4, 1, 0])
print(p)

(0 2 4)(1 3)

As you can see, sympy already prints the permutation in the equivalent cycle notation, as we have defined that in the init_printing function. You can get it directly by the cycle_form property:

p.cyclic_form

[[0, 2, 4], [1, 3]]

which is an alternative way to define the same permutation in sympy: just use a list of lists and it will be interpreted as a list of disjoint cycles:

p = Permutation([[0, 2, 4], [1, 3]])
print(p)

(0 2 4)(1 3)

To get the array form, use the array_form property:

p.array_form

[2, 3, 4, 1, 0]

Products of permutations

After performing a permutation, you could permute the result again. This is nicely captured in the notion of multiplying permutations, which works in sympy as you would intuitively expect. For example, if we define a permutation P that shifts the numbers [0, 1, 2] in a cyclic way to [1, 2, 0], then applying P twice will give us [2, 0, 1]:

p = Permutation([1, 2, 0])
print(p.array_form)

[1, 2, 0]

print((p * p).array_form)

[2, 0, 1]

print((p**2).array_form)

[2, 0, 1]

Transpositions

Sympy can break down permutations into products of transpositions. A transposition is a permutation that swaps two elements and leaves all other elements unchanged. In cycle notation, a transposition is a cycle of length 2. For example, the transposition (2 4) swaps the elements 2 and 4.

p = Permutation([[0, 2, 4], [1, 3]])
transpositions = p.transpositions()
print(transpositions)

[(0, 4), (0, 2), (1, 3)]

p2 = Permutation(range(5)) # the identity permutation
for t in transpositions:
    p2 = Permutation([t]) * p2
    
print(p2.array_form)

[2, 3, 4, 1, 0]

We can check for equality in an obvious way:

p == p2

True

Also note that in many applications, we need to determine whether a given permutation is odd or even, for example when calculating determinants. This can be easily achieved by the transpositions method. Just take the length of the result and if it is odd, then the permutation is odd, otherwise it's even.

Size and cardinality

The size of a permutation is the number of elements in the set that the permutation acts on. For example, the size of the permutation (1 2 3) is 3, because it acts on the set {1, 2, 3}.

The cardinality of a permutation is the number of distinct permutations that can be obtained by rearranging its elements. The cardinality of a permutation is always equal to the factorial of its size. For example, the permutation (1 2 3) has size 3 and cardinality 3! = 6, because there are 6 distinct ways to rearrange the elements of the set {1, 2, 3}.

In sympy, you can get both quantities in an obvious way:

p.size

5

p.cardinality

120

Conclusion

In conclusion, understanding permutations is crucial for many mathematical and scientific applications. The ability to represent permutations in various notations, such as array-notation and cyclic-notation, is essential for working with permutations effectively. The Python library, SymPy, provides powerful tools for working with permutations, including functions for constructing and manipulating permutations in different notations. By using SymPy, one can easily perform complex permutation operations and solve problems involving permutations.