Permutations and Combinations
Permutations count ordered arrangements of objects and combinations count unordered selections; together they form the elementary core of enumeration.
Definition
A permutation of a set is an ordered arrangement of its elements (or a bijection of the set to itself); a combination is an unordered selection of a fixed number of elements from a set.
Scope
This topic develops the counting of arrangements (with and without repetition), selections, and their refinements, including derangements, circular permutations, and permutations with restricted positions. It introduces permutation statistics such as descents, inversions, and cycle structure, which connect elementary counting to the richer modern theory of the symmetric group.
Core questions
- How many ways can n distinct objects be ordered, and how many ways can r of them be ordered?
- How do repetition and indistinguishability change the count of arrangements?
- What are derangements, and how often does a random permutation fix no element?
- Which statistics on permutations are equidistributed?
Key concepts
- Factorial and falling factorial
- Arrangements with and without repetition
- Derangements
- Circular permutations
- Inversions and descents
- Stirling numbers
Key theories
- Cycle decomposition of permutations
- Every permutation factors uniquely into disjoint cycles; counting permutations by their cycle type is governed by Stirling numbers of the first kind and underlies the structure of the symmetric group.
- Derangement enumeration
- The number of permutations with no fixed point, derived via inclusion-exclusion, approaches n!/e, giving the classic result that about 37% of permutations are derangements.
Clinical relevance
Permutation and combination counts appear in probability (equally likely outcomes), sorting and shuffling algorithms, experimental design, and cryptographic key spaces, where the size of an arrangement space determines difficulty and security.
History
The combinatorics of permutations was systematized by MacMahon's early-20th-century work on combinatory analysis and later deepened through the modern theory of permutation statistics.
Key figures
- Percy MacMahon
- Richard P. Stanley
Related topics
Seminal works
- stanley2011
Frequently asked questions
- How many permutations does a set of n elements have?
- It has n! permutations, the product of all positive integers up to n, since each of the n positions is filled by a distinct remaining element.
- What is a derangement?
- A derangement is a permutation in which no element remains in its original position, such as a reshuffling where no letter returns to its own envelope.