Partial permutation
Bijection between two equal-sized subsets of a finite set.
In combinatorics, a partial permutation (also called a sequence without repetition) on a finite set S is a bijection between two equally sized subsets of S. More formally, it consists of two subsets U and V of the same size, along with a one-to-one mapping from U onto V. Another way to think of it is as a partial function on S that can be completed into a full permutation.
When S is the set {1, 2, ..., n}, a partial permutation is often written as a string of n symbols. Some positions contain distinct numbers from 1 to n, while the rest hold a special "hole" symbol (◊). The positions without holes form the domain U, and each such position maps to the number written there. For example, the string "1 ◊ 2" represents a partial permutation where 1 maps to itself and 3 maps to 2. The seven partial permutations on two items are: ◊◊, ◊1, ◊2, 1◊, 2◊, 12, 21.
The number of partial permutations on n items grows quickly. For n = 0, 1, 2, 3, ... the counts are 1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114, 234662231, ... (OEIS sequence A002720). This number can be found by summing i! times the square of the binomial coefficient (n choose i) from i = 0 to n, where each term counts partial permutations with exactly i non-hole entries. It also satisfies the recurrence P(n) = 2n P(n−1) − (n−1)² P(n−2). This recurrence comes from considering cases: P(n−1) partial permutations where the final elements of both sets are omitted; another P(n−1) where the final elements map to each other; (n−1)P(n−1) where the final element of the first set is included but does not map to the final element of the second; another (n−1)P(n−1) where the final element of the second set is included but does not map to the final element of the first; and subtracting (n−1)² P(n−2) to remove those counted twice—where both final elements are included but do not map to each other.
Some authors restrict partial permutations so that either the domain or the range must be the first k items of the n-item set. In the first case, a partial permutation of length k from an n-set is simply a sequence of k distinct terms from the set (sometimes confusingly called a "k-permutation" in elementary combinatorics).
- field
- Combinatorial mathematics
- known_for
- Partial permutations, sequences without repetition, bijections between subsets
- representation
- String of n symbols with distinct numbers and hole symbol ◊
- summation_formula
- ∑_{i=0}^n i! (n choose i)^2
- recurrence_relation
- P(n) = 2n P(n-1) - (n-1)^2 P(n-2)
Lore & Background
Partial permutations are most often studied on the set {1, 2, ..., n}. In this standard representation, a partial permutation is written as a string of n symbols, where each position either holds a distinct integer from 1 to n or a special "hole" symbol (◊). The positions without holes form the domain of the partial permutation, and the number written in a given position indicates the image of that position under the mapping. For example, the string "1 ◊ 2" represents a partial permutation that sends position 1 to the number 1 and position 3 to the number 2. For two items, the seven possible partial permutations are: ◊◊, ◊1, ◊2, 1◊, 2◊, 12, and 21. The total number of partial permutations on n items follows a known integer sequence: for n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, the counts are 1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114, and 234662231. This number can be calculated by summing over all possible support sizes (the number of non-hole entries), or by a recurrence relation that considers whether the final elements of each set are omitted, map to each other, or are included but map elsewhere. Some authors restrict partial permutations so that either the domain or the range must consist of the first k items of the n-set. In the former case, the object is simply a sequence of k distinct terms from the n-set, sometimes called a "k-permutation" in elementary combinatorics.
Reader's Guide
(OEIS A002720). The nth term is computed by the summation ∑_{i=0}^n i! (n choose i)^2, where the ith term counts partial permutations with support of size i (i non-hole entries). Alternatively, it satisfies the recurrence P(n) = 2n P(n-1) - (n-1)^2 P(n-2). This recurrence is derived by considering cases involving the final elements of each set: P(n-1) partial permutations where final elements are omitted; P(n-1) where they map to each other; (n-1)P(n-1) where the final element of the first set is included but does not map to the final element of the second; (n-1)P(n-1) where the final element of the second set is included but does not map to the final element of the first; and subtracting (n-1)^2 P(n-2) for those counted twice where both final elements are included but do not map to each other. Some authors restrict partial permutations so that either the domain or the range is forced to consist of the first k items, yielding a sequence of k terms from an n-set without repetition, sometimes called 'k-permutations'.
Did You Know?
- A partial permutation can be represented by a string of n symbols with distinct numbers and a special 'hole' symbol ◊.
- The number of partial permutations on n items follows the recurrence P(n) = 2n P(n-1) - (n-1)^2 P(n-2).
- The seven partial permutations on two items are: ◊◊, ◊1, ◊2, 1◊, 2◊, 12, 21.
Frequently Asked Questions
Who is Partial permutation?
In combinatorial mathematics, a partial permutation is a bijection between two specified subsets U and V of a finite set S, where U and V have equal cardinality. Equivalently, it is a partial function on S that can always be extended to a full permutation of the entire set.
What are Partial permutation's powers/role?
Its primary role is in combinatorial enumeration and representation: it is commonly encoded as a string of n distinct symbols with a special 'hole' marker (◊) indicating the positions not covered by the mapping. This makes it a natural bridge between sequences without repetition and full permutations.
What recurrence relation does Partial permutation satisfy?
The numbers obey P(n) = 2n · P(n−1) − (n−1)² · P(n−2), allowing each term to be generated from the two preceding ones without re-summing the full formula.
Why is Partial permutation important in combinatorics?
It generalizes the notion of a permutation by allowing the domain and codomain to be proper subsets, which makes it a key object for studying partial bijections, sequence enumeration, and the combinatorial structure underlying permutation groups. Its clean enumeration formula and recurrence make it a standard benchmark in enumerative combinatorics.
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