1 Basic concepts

Permutation is one of the central ideas in combinatorics and algebra. It refers to an ordered arrangement of objects, or more abstractly to a rearrangement of elements within a set. Because order is significant, two arrangements that contain the same objects may still be different permutations if the positions of the objects differ.

Permutations provide a natural way to describe counting problems, symmetry operations, and transformations that preserve a set while reshuffling its elements. They also appear in group theory, where permutations can be combined and studied as algebraic objects.

1.1 Definition

A permutation is an arrangement of a collection of distinct objects in a specific order. If the objects are labeled, then a permutation assigns each object to a position in a sequence. In abstract settings, the term may also mean a bijective mapping from a set to itself, meaning every element is moved to exactly one image and every image has exactly one preimage.

This dual meaning is common in mathematics. In counting, a permutation emphasizes an ordered listing. In algebra, it emphasizes the rearrangement function.

1.2 Order and arrangement

The defining feature of a permutation is order. For example, the sequence ABC is different from BAC, even though both contain the same three letters. The arrangement determines the permutation, not merely the collection of items.

This sensitivity to order distinguishes permutations from many other ways of selecting objects. In practical problems, the position of each element often matters as much as the element itself, which is why permutations arise whenever sequence, ranking, or arrangement is involved.

1.3 Permutations versus combinations

Permutations and combinations are related but distinct. A combination is a selection in which order does not matter, while a permutation is an arrangement in which order does matter. Choosing three books from a shelf gives a combination; placing those same three books in a row gives a permutation.

When a problem asks how many ways objects can be chosen and ordered, permutations are the relevant concept. When only membership matters, combinations are used instead.

1.4 Notation and terminology

Permutations are often written as ordered lists, such as 1, 2, 3 or A, C, B. In algebra, they may be described using cycle notation, which records how elements are moved. The language of “arrangement,” “reordering,” “transposition,” and “cycle” is common in this area.

The word permutation comes from the idea of changing things around. In formal mathematics, it usually implies a one-to-one correspondence within a set, especially when the set is finite.

2 Counting permutations

Counting permutations is a standard topic in combinatorics. The number of possible arrangements depends on whether the objects are distinct, repeated, selected only in part, or arranged around a circle. Each of these cases has its own formula and interpretation.

2.1 Permutations of distinct objects

If a set contains distinct objects and all of them are arranged, the number of possible permutations is the total number of different orders. Each position can be filled by one of the remaining objects, so the count grows rapidly as the number of objects increases.

2.1.1 Factorial formula

For n distinct objects, the number of permutations is n!, read as “n factorial.” This means

n! = n × (n - 1) × (n - 2) × ... × 2 × 1.

The factorial formula reflects the successive choices available for each position. After one object is placed, fewer remain for the next position, and so on.

2.1.2 Examples

Three distinct objects have 3! = 6 permutations. For example, the letters A, B, and C can be arranged as ABC, ACB, BAC, BCA, CAB, and CBA.

With four objects, there are 4! = 24 permutations. Even small increases in the number of objects produce much larger counts, which is why permutation problems often involve quickly growing totals.

2.2 Permutations with repeated objects

When some objects are identical, not every rearrangement produces a new arrangement. Swapping two identical items does not create a distinct permutation, so the total count must be adjusted.

2.2.1 Multiset permutations

For a collection with repeated elements, the number of distinct permutations is found by dividing the factorial of the total number of objects by the factorials of the repetition counts. If a set of n objects contains groups of repeated items of sizes n1, n2, and so on, then the number of distinct arrangements is

n! / (n1! n2! ...).

This formula is used for multisets, where elements may appear more than once. It accounts for indistinguishable rearrangements that would otherwise be overcounted.

2.3 Partial permutations

Sometimes only part of a set is arranged. In that case, a permutation may refer to choosing and ordering a subset rather than using every available object.

2.3.1 Arrangements of r objects from n

The number of ways to arrange r objects chosen from n distinct objects is

n! / (n - r)!.

This count is sometimes called a permutation of n objects taken r at a time. It applies when order matters but not all objects are used. For example, selecting a first, second, and third place from a group of competitors is a partial permutation problem.

2.4 Circular permutations

When objects are arranged around a circle, the count changes because rotations that produce the same visible order are not considered distinct. The circular setting removes a reference point that would otherwise distinguish one arrangement from another.

2.4.1 Rotational equivalence

For n distinct objects arranged in a circle, the number of distinct circular permutations is (n - 1)!. This is because one object can be fixed in place, and the others can then be arranged relative to it.

Rotations of the same circular arrangement are treated as equivalent. This idea is common in seating problems and in studies of cyclic symmetry.

3 Types of permutations

Permutations can be classified by how they move elements. Some leave everything unchanged, some exchange two elements, and others move several elements in a cycle. These types are important for both counting and algebraic analysis.

3.1 Identity permutation

The identity permutation leaves every element in its original position. It is the simplest permutation and serves as the neutral element under composition.

In notation, the identity often appears as a mapping that sends each element to itself. In cycle notation, it may be written as a product of empty or one-element cycles, depending on convention.

3.2 Transpositions

A transposition is a permutation that exchanges exactly two elements and leaves all others fixed. It is one of the most basic nontrivial permutations.

Transpositions are important because many permutations can be built from them. They also play a key role in determining whether a permutation is even or odd.

3.3 Cycles

A cycle is a permutation that moves a sequence of elements in a closed loop. For example, one element may move to the position of another, which moves to a third, and so on, until the last returns to the first.

Cycles provide a compact way to describe how a permutation acts. They make it easier to see which elements move together and which remain fixed.

3.3.1 Cycle notation

Cycle notation writes a permutation by listing the elements moved in a cycle, such as (1 3 2). This indicates that 1 moves to 3, 3 moves to 2, and 2 moves back to 1.

Cycle notation is concise and widely used in abstract algebra. It emphasizes the action of the permutation rather than the complete list of images.

3.3.2 Disjoint cycles

Two cycles are disjoint if they move different sets of elements. A permutation can often be written as a product of disjoint cycles, which makes its structure easier to analyze.

Disjoint cycles commute with one another because they act on separate elements. This decomposition is unique up to the order in which the cycles are written.

3.4 Even and odd permutations

A permutation is even if it can be expressed as a product of an even number of transpositions, and odd if it requires an odd number. This classification is fundamental in algebra and depends only on the permutation itself, not on a particular decomposition.

Even and odd permutations divide the symmetric group into two large classes. This distinction is closely tied to the sign of a permutation and to determinant theory in linear algebra.

4 Permutations in algebra

In algebra, permutations are treated as functions that can be composed, inverted, and organized into groups. This perspective reveals a rich structure that connects permutations to symmetry and transformation.

4.1 Permutation groups

A permutation group is a set of permutations closed under composition and inverses. Such groups capture the symmetries of finite sets and many other structured objects.

Permutation groups are central in group theory because every finite group can be represented as a group of permutations through a standard theorem. This makes them a universal model for abstract group behavior.

4.1.1 Symmetric groups

The symmetric group on n elements, usually written S_n, is the group of all permutations of n objects. It has n! elements and includes every possible reordering of the set.

Symmetric groups are among the most studied examples in algebra. They serve as a basic setting for understanding composition, parity, and group action.

4.1.2 Subgroups of permutations

A subgroup of a permutation group is a smaller collection of permutations that still satisfies the group properties. Such subgroups may reflect special symmetries or restricted movement of elements.

Studying subgroups helps reveal the internal structure of a larger permutation group. They often arise from constraints such as preserving certain blocks, patterns, or partitions of the underlying set.

4.2 Composition of permutations

Composition is the operation of applying one permutation after another. If one permutation rearranges a set and a second permutation acts on the result, their composition is again a permutation.

This operation is not generally commutative: the order in which permutations are composed matters. That feature distinguishes permutation algebra from ordinary arithmetic and gives the subject much of its richness.

4.3 Inverse permutations

Every permutation has an inverse, which reverses its action. If one permutation sends each element to a new position, the inverse sends each element back to its original position.

The existence of inverses follows from the fact that permutations are bijections. In cycle notation, the inverse of a cycle is obtained by reversing the direction of the cycle.

4.4 Permutation matrices

A permutation matrix is a square matrix with exactly one entry of 1 in each row and each column, and 0s elsewhere. It represents a permutation in linear algebraic form.

Multiplying by a permutation matrix reorders coordinates or basis vectors. These matrices are useful because they translate permutation problems into matrix operations, making them accessible to linear algebra methods.

5 Properties and operations

Permutations have several measurable features that help classify and analyze them. These include fixed points, inversions, parity, and the pattern of cycles in their decomposition.

5.1 Fixed points

A fixed point is an element that remains in the same position under a permutation. If a permutation sends x to x, then x is fixed.

Fixed points are often important in counting and in the study of symmetry. A permutation may move some elements while leaving others unchanged, and the number of fixed points can carry significant combinatorial information.

5.2 Sign of a permutation

The sign of a permutation is either +1 or -1, depending on whether the permutation is even or odd. It provides a compact algebraic summary of parity.

This sign behaves multiplicatively under composition. It is closely connected to determinants and to the alternation of terms in algebraic formulas.

5.3 Inversions

An inversion is a pair of elements that appear in the opposite order from the natural or expected order after a permutation is applied. The number of inversions gives another way to measure how far a permutation is from the identity.

Counting inversions is useful in determining parity, since a permutation is even or odd according to whether the inversion count is even or odd. Inversions also appear in sorting algorithms and related computational contexts.

5.4 Cycle structure

The cycle structure of a permutation describes how its elements break into cycles, including the lengths of those cycles. This structure is a key invariant for many purposes.

Two permutations with the same cycle structure share several algebraic properties, though they need not be identical. Cycle structure helps classify permutations and understand their repeated action.

6 Applications

Permutations appear in many branches of mathematics and in practical areas that depend on ordering, arrangement, and transformation. Their usefulness comes from the fact that many problems can be modeled as reordering a finite set.

6.1 Combinatorics

In combinatorics, permutations are used to count arrangements, rankings, and ordered selections. They form the basis for many standard counting principles.

Permutation methods also support more advanced topics such as inclusion-exclusion, generating functions, and enumerative formulas involving ordered structures.

6.2 Cryptography

In cryptography, permutations are used to rearrange data, permute bits, or design components of encryption systems. They can contribute to confusion and diffusion, which are desirable properties in secure designs.

Permutation-based operations often appear in block ciphers and other algorithmic systems where structured reordering helps obscure patterns in the input.

6.3 Coding theory

In coding theory, permutations can describe reordering of code symbols or coordinates. Certain codes remain unchanged under specific permutations, which can reveal useful symmetry.

Permutation techniques may also help in decoding strategies, where rearranging positions simplifies analysis or comparison of code words.

6.4 Symmetry and group actions

Permutations are a natural way to represent symmetry. When a set of objects has a pattern that remains unchanged under certain rearrangements, those rearrangements can be modeled as permutations.

Group actions often use permutations to describe how a group moves elements of a set. This connection makes permutations a bridge between concrete arrangements and abstract symmetry.

Several topics are closely connected to permutations. Some concern the symbols and conventions used to write them, while others extend the idea into algebra, statistics, and polynomial maps.

7.1 Permutation notation

Permutation notation includes ordinary list notation, cycle notation, and matrix notation. Each emphasizes a different aspect of the same underlying rearrangement.

The choice of notation depends on context. Cycle notation is efficient in abstract algebra, while list notation is often easier in elementary counting problems.

7.2 Permutation polynomials

A permutation polynomial is a polynomial that induces a permutation of the elements of a finite set, typically a finite field. It maps each element to a unique image without repetition.

These polynomials are studied in algebra and number theory, where they connect polynomial structure with bijective behavior on finite domains.

7.3 Permutation tests in statistics

Permutation tests are statistical methods that assess significance by comparing observed data with many rearranged versions of the same data. The rearrangements simulate what would be expected under a null hypothesis.

These tests are valued for their flexibility and minimal assumptions. They use the logic of permutations to generate reference distributions directly from the data.