Permutation
A bijection rearranging a set's elements into a new order.
A permutation is a bijection of a set onto itself, meaning a one-to-one correspondence that maps each element of the set to a unique element of the same set. This mathematical concept can be understood in two primary ways. The first interpretation treats a permutation as a new linear order or sequence of the set's members. For instance, the set {1, 2, 3} has six possible ordered arrangements: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). Each of these tuples corresponds to a specific bijection that sends the numbers 1, 2, and 3 to the first, second, and third positions of the tuple, respectively. Anagrams of words with all distinct letters are also permutations, as they reorder the original sequence of letters. The second interpretation defines a permutation as a function from a set to itself where every element appears exactly once as an image value. Such a function is equivalent to a rearrangement where each element i is replaced by its image under the function. The collection of all permutations of a set forms a group, known as the symmetric group, under the operation of function composition. In elementary combinatorics, partial permutations, or k-permutations, are ordered arrangements of k distinct elements selected from a larger set. The number of permutations of n distinct objects is given by n factorial, the product of all positive integers from 1 to n. The study of permutations is central to combinatorics and group theory, with applications in analyzing sorting algorithms, describing particle states in quantum physics, and modeling RNA sequences in biology. Historically, permutation-like hexagrams appeared in the I Ching around 1000 BC. Xenocrates of Chalcedon attempted to count Greek syllables, while the Arab mathematician Al-Khalil listed all possible Arabic words. Bhāskara II’s Lilavati described the factorial rule around 1150 AD. Fabian Stedman explained factorials through bell ringing in 1677, using a recursive "casting away" method. Joseph Louis Lagrange linked permutations of polynomial roots to solvability, leading to Galois theory. Permutations also proved crucial in cryptanalysis of the Enigma machine during World War II.
- field
- Mathematics
- known_for
- Study of permutations as bijections and ordered arrangements; foundation of symmetric groups and Galois theory
- related_concepts
- Factorial, symmetric group, composition of functions, cycle type
Lore & Background
In mathematics, a permutation is a bijection of a set onto itself, which can be understood either as a new order of the members of a sequence or as the act of changing that order. For example, the six permutations of the set {1, 2, 3} are the six 3-tuples (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), and (3,2,1). These correspond to the six bijections that map each element to its position in the tuple. Anagrams of words with all distinct letters are also permutations, as they reorder the original letters. The number of permutations of n distinct objects is n factorial, the product of all positive integers up to n. In the second sense, a permutation is a function from a set to itself where every element appears exactly once as an image; such a function is equivalent to a rearrangement where each element i is replaced by its image. The collection of all permutations of a set forms a group, the symmetric group, under composition of functions. In elementary combinatorics, k-permutations are ordered arrangements of k distinct elements selected from a set; when k equals the set’s size, these are full permutations. Permutation-like objects, called hexagrams, appeared in the I Ching in China as early as 1000 BC. In Greece, Plutarch reported that Xenocrates of Chalcedon discovered the number of different syllables possible in Greek. The Arab mathematician Al-Khalil wrote the first known work using permutations and combinations to list all possible Arabic words. By around 1150 AD, Indian mathematician Bhāskara II’s Lilavati described the rule for counting permutations. In 1677, Fabian Stedman explained factorials in the context of change ringing bells, using a recursive “casting away” method. Around 1770, Joseph Louis Lagrange linked permutations of polynomial equation roots to solvability, leading to Galois theory. Cauchy’s 1815 memoir on permutations as substitutions helped establish the concept of a group. Permutations were also crucial in cryptanalysis of the Nazi Enigma machine, notably because two permutations are conjugate exactly when they share the same cycle structure.
Reader's Guide
In mathematics, a permutation is a bijection of a set onto itself, representing either a new order of a sequence or the act of changing that order. The study of permutations of finite sets is central to combinatorics and group theory, and it appears in nearly every branch of mathematics as well as in other sciences. In computer science, permutations are used to analyze sorting algorithms; in quantum physics, they describe the states of particles; and in biology, they help describe RNA sequences. The collection of all permutations of a set forms a group, known as the symmetric group, where the group operation is the composition of functions—performing one rearrangement after another to yield a new rearrangement. Historically, permutation-like concepts appeared in ancient China in the I Ching around 1000 BC. In Greece, Xenocrates of Chalcedon attempted to count the number of different syllables in Greek. The Arab mathematician Al-Khalil wrote the Book of Cryptographic Messages, which used permutations and combinations to list all possible Arabic words. By 1150 AD, Indian mathematician Bhāskara II’s Lilavati described the rule for determining the number of permutations of n objects. In 1677, Fabian Stedman explained factorials through the number of permutations of bells in change ringing, using a recursive “casting away” method. Around 1770, Joseph Louis Lagrange connected permutations of polynomial roots to the solvability of equations, a line of work that led to Galois theory. Permutations as substitutions on n elements also helped establish the concept of a group as an algebraic structure, notably through Cauchy’s 1815 memoir. They were crucial in cryptanalysis of the Enigma machine, where the conjugacy of permutations—two permutations being conjugate exactly when they share the same structure—was a key property.
Did You Know?
- The number of permutations of n distinct objects is n factorial (n!).
- The collection of all permutations of a set forms a group called the symmetric group.
Frequently Asked Questions
What is a Permutation?
A Permutation is a one-to-one mapping that takes every element of a set and reorders them back into the same set. Think of it as shuffling a deck of cards so each card still appears exactly once, just in a different position.
What role does Permutation play in group theory?
Permutations form the backbone of symmetric groups, where every possible rearrangement of a finite set is treated as a group element. They give mathematicians the language for describing symmetry, composition, and cycle structure across the field.
How is Permutation connected to Factorial?
The total number of distinct Permutations of a set with n elements is exactly n!, the factorial of n. This link is the combinatorial reason factorials pop up so often in counting problems.
Why is Permutation considered foundational in combinatorics?
Nearly every ordered-arrangement question in combinatorics reduces to understanding how elements can be bijectively rearranged. It also underpins Galois theory, where the solvability of polynomial equations hinges on the structure of permutation groups.
Where does Permutation show up outside pure math?
Permutations appear in computer science (sorting, hashing), quantum physics (particle exchange symmetries), and biology (gene ordering and recombination). Their study of how ordered arrangements transform is a universal tool across all these fields.
More in Combinatorics 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record