Partial permutation
Bijection between two equal-sized subsets of a finite set.
In combinatorial mathematics, a partial permutation, or sequence without repetition, on a finite set S is a bijection between two specified subsets of S. It is defined by two subsets U and V of equal size, and a one-to-one mapping from U to V. Equivalently, it is a partial function on S that can be extended to a permutation. Partial permutations are studied for their combinatorial enumeration and representation, often using a string of symbols with a special 'hole' symbol to denote missing entries.
- 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 commonly considered when the set S is {1, 2, ..., n}. In this case, a partial permutation may be represented by a string of n symbols, some of which are distinct numbers from 1 to n, and the remaining ones are a special 'hole' symbol ◊. The domain U consists of the positions without a hole, and each such position maps to the number in that position. For example, the string '1 ◊ 2' represents a partial permutation mapping 1 to itself and 3 to 2. The seven partial permutations on two items are: ◊◊, ◊1, ◊2, 1◊, 2◊, 12, 21.
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
Elsewhere in the Combinatorics universe
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