AlegsaOnline.com

Permutations — ordered arrangements, counting formulas, and common representations

Overview of permutations: ordered arrangements of distinct items, counting formulas (n!, multinomial), transpositions, cycle and list representations, and common examples in math, CS, and statistics.

Author: Leandro Alegsa Creation date: November 13, 2022 Last updated: April 10, 2026

en.wikipedia.org · Public domain

Permutation describes one specific ordering of the elements in a set. In other words, if you have a collection of distinct items, a permutation is a particular sequence that lists those items in a chosen order. The concept is widely used in mathematics and in many applied fields such as computer science and statistics.

Definition and basic idea

Think of a permutation as an arrangement or lineup. For a given set of objects, each different arrangement counts as a different permutation. Swapping the positions of two items produces a different permutation; similarly, moving an item to a new position while shifting others yields another permutation.

Counting permutations

If there are n distinct objects, the total number of possible permutations of all n objects is n factorial, written n!, which equals 1·2·3·…·n. For example, three distinct items can be ordered in 3! = 6 different ways.

When some objects are identical, the number of distinct permutations is smaller. If n items include groups of identical objects of sizes n1, n2, ..., nk (with n1 + n2 + … + nk = n), the number of distinct orderings is

n! / (n1! n2! … nk!),

because permutations that only swap identical items do not create new, distinguishable arrangements.

Common examples

Seating arrangements: the different ways people can sit in fixed seats around a table or in a car are permutations of the people.
Words and letters: different orderings of letters form different strings; for example, the letters A, B, C have six permutations: ABC, ACB, BAC, BCA, CAB, CBA.

Additional notes

A simple swap of two elements is called a transposition. Any permutation can be built as a sequence of transpositions.
There are multiple ways to represent a permutation: as a list showing the image of each position, or in cycle notation, which groups elements according to how they are moved among positions.

All six permutations of three colored balls

Combinatorial basics

Problem

A permutation is an arrangement of objects in a particular order or a rearrangement of objects from a given order. Examples of permutations are:

An anagram is a permutation of the letters of a word, such as ENKEL and NELKE.
Shuffling the cards of a deck results in a (ideally) random permutation of the cards.
In volleyball, the change of position after conquering the right of serve is a cyclical permutation of the players.
Many sorting methods work with successive transpositions, i.e. permutations that swap exactly two objects.

If not all objects are selected in such an arrangement, one speaks of a variation instead of a permutation; if the order does not play a role in the selection, one speaks of a combination. In counting combinatorics, the question now arises as to the number of possible permutations. Here we distinguish the case in which all objects are different from the case in which some of the objects are identical.

Permutation without repetition

A permutation without repetition is an arrangement of objects, all of which are distinguishable. After there are placement possibilities for the first object, there are only n-1 possibilities for the second object, only possibilities for the third n-2 object, and so on until the last object, which has only one free space left. The number of possible permutations of objects is thus given by the factorial

$n!=n\cdot (n-1)\cdot (n-2)\cdot \ldots \cdot 1$

indicated.

For example, there are $4!=4\cdot 3\cdot 2\cdot 1=24$ possible arrangements of four different colored balls in a row.

Permutation with repetition

A permutation with repetition is an arrangement of objects, some of which are indistinguishable. If exactly objects are identical, then they are permutable in their places without resulting in a new order. In this way, exactly arrangements are the same. Thus, the number of permutations of objects of which are identical is given by the falling factorial

${\frac {n!}{k!}}=n\cdot (n-1)\cdot \ldots \cdot (k+1)=n^{\underline {n-k}}$

Given. If there are not only one, but groups with $k_{1},\ldots ,k_{s}$ identical objects each, then all these objects can be swapped in their places without resulting in new arrangements. If we also count the objects that occur only once with multiplicity , then $k_{1}+\ldots +k_{s}=n$ and the number of possible permutations is given by the multinomial coefficient

${\frac {n!}{k_{1}!\cdot \ldots \cdot k_{s}!}}={\binom {n}{k_{1},\ldots ,k_{s}}}$

specify.

For example, there are ${\tfrac {4!}{2!\,1!\,1!}}={\tfrac {24}{2}}=12$ possible arrangements of four colored balls in a row if exactly two of the balls have the same color, and ${\tfrac {4!}{2!\,2!}}={\tfrac {24}{4}}=6$ possible arrangements when each two balls are of the same color.

Algorithms

A number of algorithms exist for the systematic generation of all permutations of n elements, which can often be well formulated recursively. These include, among others, the Steinhaus-Johnson-Trotter algorithm and the heap algorithm.

Permutations of four colored spheres without repetition (left) and with repetition (middle and right).

Definition

Let $X=\{x_{1},x_{2},\ldots ,x_{n}\}$ be a set with elements, then an -digit permutation (without repetition) is a bijective mapping

$\pi \colon X\rightarrow X$ ,

which assigns to each element of the set an element of the same set. Clearly, by permutation, each element $x_{i}$ for $i=1,\ldots ,n$ takes the place of its associated element π $\pi (x_{i})$ . Due to the bijectivity of the mapping, two different elements are never mapped to the same element in this case. The case n=0 is also allowed and is then the empty set.

Since, by definition, any finite set to a set of the form {1, 2, ..., n} is equipotent, one can always restrict the mathematical consideration of permutations to the first natural numbers as the reference set. A permutation is then a bijective mapping

$\pi \colon \{1,2,\ldots ,n\}\rightarrow \{1,2,\ldots ,n\}$ ,

which assigns to each natural number between and exactly one number in the same range. If we imagine all numbers lined up in a list, then the number takes the place with the number π $\pi (j)$ $j\in \{1,\ldots ,n\}$ by permutation.

Author

AlegsaOnline.com - Permutation - Leandro Alegsa

Creation date: November 13, 2022
Last updated: April 10, 2026

URL: https://en.alegsaonline.com/art/75877