Partial permutation
A partial permutation on a finite set X is a bijection between two subsets of X of equal cardinality, generalizing the notion of a full permutation, which is a bijection from X to itself.[1] The domain and range of such a bijection are denoted \operatorname{dom}(p) and \operatorname{ran}(p), respectively, and may be empty or proper subsets.[1] In combinatorics, partial permutations are enumerated by considering the size k of the subsets involved; the total number of partial permutations on a set of n elements is \sum_{k=0}^{n} \binom{n}{k}^2 k!, which counts the ways to choose the domain and range subsets of size k and then pair them bijectively.[2] Special cases include monotonic partial permutations, numbering \binom{2n}{n}, and decreasing partial permutations, numbering the (n+1)-th Bell number B_{n+1}.[2] Composition of partial permutations is defined where possible, as (p \circ q)(x) = p(q(x)) for x in the appropriate overlapping domain, forming structures like inverse semigroups when closed under this operation and including the identity.[2] Any partial permutation can be extended to a full permutation of X.[1] Partial permutations play a key role in permutation group theory and computational algebra, where they represent elements in systems like the GAP software for handling symmetric groups and their extensions.[3] They also arise in applications such as comparing gene sequences in bioinformatics, data augmentation for image processing via color transformations, and solving parameterized dictionary matching problems in string algorithms.[4] Problems involving agreement or extension of sets of partial permutations are studied for their computational complexity, often linking to conjectures like the Strong Exponential Time Hypothesis.[4]Definition and Basics
Formal Definition
A partial permutation on a finite set S is defined as a bijection \pi: A \to B, where A and B are subsets of S such that |A| = |B| = k \leq |S|.[1] This structure ensures that \pi is one-to-one and onto between the specified subsets, capturing a matching of k elements from S to itself without requiring full coverage of S.[4] The domain of \pi, denoted \dom(\pi), is the subset A \subseteq S on which \pi is defined, while the range, denoted \ran(\pi), is the subset B \subseteq S that serves as the image of A under \pi.[1] The size of the partial permutation is given by k = |\dom(\pi)| = |\ran(\pi)|, representing the number of elements actively mapped by \pi.[4] For instance, consider S = \{1, 2, 3\} and the mapping \pi that sends $1 to $3 while leaving $2 and $3 undefined in the domain; here, \dom(\pi) = \{1\}, \ran(\pi) = \{3\}, and the size is k=1.[1] Partial permutations are frequently studied in the context of the set = \{1, 2, \dots, n\}, where S = . Unlike a general injection from a subset of S into S, a partial permutation specifically requires the mapping to be a bijection onto its range subset, ensuring an exact correspondence between domain and range.[1] Full permutations arise as the special case where \dom(\pi) = \ran(\pi) = S.[4]Relation to Permutations
Partial permutations generalize the concept of full permutations by allowing the mapping to apply only to a proper subset of the elements, rather than the entire set. Specifically, a full permutation of a set S of size n is equivalent to an n-partial permutation on S, where the domain and range both coincide with S.[5] Note that in some combinatorial contexts, particularly in permutation pattern avoidance, "partial permutations" alternatively refer to injections from to, which are ordered selections of k distinct elements from $$ (counted by P(n,k) = \frac{n!}{(n-k)!}). This differs from the bijection-between-subsets definition used here.[6]Properties
Structural Properties
A partial permutation on a finite set X is defined as a bijection \pi: \dom(\pi) \to \ran(\pi), where \dom(\pi) and \ran(\pi) are subsets of X with equal cardinality k = |\dom(\pi)| = |\ran(\pi)|.[1][4] By this definition, \pi is injective on its domain, meaning distinct elements in \dom(\pi) map to distinct elements in \ran(\pi), and surjective onto its range, meaning every element in \ran(\pi) is the image of exactly one element in \dom(\pi).[1][4] The support of a partial permutation \pi, denoted \supp(\pi), is the union \dom(\pi) \cup \ran(\pi), which captures all elements of X involved in the mapping.[7] The size of the support satisfies k \leq |\supp(\pi)| \leq 2k, since |\supp(\pi)| = 2k - |\dom(\pi) \cap \ran(\pi)|, with equality to k occurring when \dom(\pi) = \ran(\pi).[4] For a partial permutation of size k on the set = \{1, 2, \dots, n\} with n \geq 2k, the possible supports are subsets of $$ of size between k and $2k, chosen such that there exist subsets A, B \subseteq S (not necessarily disjoint) with |A| = |B| = k and A \cup B = S. For example, on {{grok:render&&&type=render_inline_citation&&&citation_id=5&&&citation_type=wikipedia}} with k=2, a possible support is \{1,2,3\}, where \dom(\pi) = \{1,2\} and \ran(\pi) = \{2,3\}, allowing mappings like \pi(1)=2, \pi(2)=3.[4] Fixed points of \pi are elements x \in \dom(\pi) \cap \ran(\pi) such that \pi(x) = x.[3] These arise naturally when the domain and range overlap, and the number of fixed points is the size of the set \{x \in \dom(\pi) \cap \ran(\pi) \mid \pi(x) = x\}. In the identity partial permutation on a subset A \subseteq X with \dom(\pi) = \ran(\pi) = A, every element of A is a fixed point.[1] A fundamental structural theorem states that any partial permutation on a finite set can be extended to a full permutation of the entire set. Specifically, given \pi: A \to B with A, B \subseteq X and |A| = |B| = k < |X|, there exists a permutation \sigma of X such that \sigma extends \pi, meaning A \subseteq \dom(\sigma) and \sigma(a) = \pi(a) for all a \in A. This extension is not unique in general but always exists, for example by choosing any bijection from X \setminus \dom(\pi) to X \setminus \ran(\pi).[1] Conversely, any injective mapping f: S \to T between finite subsets S, T \subseteq X with |S| = |T| uniquely defines a partial permutation with \dom(f) = S and \ran(f) = T, as the bijectivity follows directly from the injectivity and equal cardinalities.[4]Operations on Partial Permutations
Partial permutations, as bijections between subsets of a finite set, support several key operations that preserve their bijective nature. The primary operation is composition, which combines two partial permutations \pi_1 and \pi_2 on a set X. The composition \pi_1 \circ \pi_2 is defined on the subset of \dom(\pi_1) where \pi_1(x) \in \dom(\pi_2), with (\pi_1 \circ \pi_2)(x) = \pi_2(\pi_1(x)) for such x. Thus, \dom(\pi_1 \circ \pi_2) = \pi_1^{-1}(\dom(\pi_2) \cap \ran(\pi_1)) and \ran(\pi_1 \circ \pi_2) = \pi_2(\dom(\pi_2) \cap \ran(\pi_1)), ensuring the result remains a partial permutation with rank at most the minimum of the ranks of \pi_1 and \pi_2.[8] If \ran(\pi_1) \cap \dom(\pi_2) = \emptyset, standard composition yields the empty partial permutation unless the domains and ranges are structured to allow partial overlap; however, in cases of disjoint supports (where \dom(\pi_1) \cap \dom(\pi_2) = \emptyset and \ran(\pi_1) \cap \ran(\pi_2) = \emptyset), the disjoint union operation defines a new partial permutation as the union of their graphs, resulting in a larger bijection with rank equal to the sum of the individual ranks. Another fundamental operation is inversion. For a partial permutation \pi, its inverse \pi^{-1} is the unique partial permutation satisfying \pi \circ \pi^{-1} = \id_{\ran(\pi)} and \pi^{-1} \circ \pi = \id_{\dom(\pi)}, where \id denotes the identity on the respective subsets. Here, \dom(\pi^{-1}) = \ran(\pi) and \ran(\pi^{-1}) = \dom(\pi), with \pi^{-1}(y) = x if \pi(x) = y. This operation swaps the domain and range while preserving bijectivity.[8] Extension provides a way to enlarge a partial permutation while maintaining its properties. Given a partial permutation \pi of rank k on a set X with |X| > k, an extension to rank k+1 is obtained by selecting an element i \in X \setminus \dom(\pi) for the domain and j \in X \setminus \ran(\pi) for the range, then adding the mapping i \mapsto j to \pi. The resulting function remains a bijection between the enlarged subsets. This process can be repeated until the rank reaches |X|, potentially yielding a full permutation. For example, consider X = \{1,2,3,4\} and \pi_1: 1 \mapsto 2, a rank-1 partial permutation. Composing with \pi_2: 2 \mapsto 3 (rank 1, with overlap) gives \pi_1 \circ \pi_2: 1 \mapsto 3 (rank 1). If instead \pi_3: 3 \mapsto 4 (disjoint support), their disjoint union is $1 \mapsto 2, 3 \mapsto 4 (rank 2). Extending \pi_1 by adding $3 \mapsto 4 yields the same rank-2 partial permutation. In non-disjoint cases, such as composing \pi_1 with \pi_4: 2 \mapsto 1 (overlap but cycle), the result is the empty partial permutation since \ran(\pi_1) \cap \dom(\pi_4) = \{2\} but the preimage domain is non-empty only if compatible, here reducing rank to 0.[9] The collection of all partial permutations on a finite set X with |X| = n, denoted I_n, forms an inverse monoid under the above composition operation, including the identity partial permutation (full bijection on X) as the unit and the empty map as a zero element. This structure is closed under composition and inversion, with every element idempotent in its local sense, and |I_n| = \sum_{k=0}^n \binom{n}{k}^2 k!.[9]Representations
Bijection Representation
A partial permutation can be viewed as a bijection \pi: A \to B, where A, B \subseteq S for a finite set S = \{1, 2, \dots, n\} and |A| = |B|, with \pi being one-to-one and onto between these subsets.[1] This representation emphasizes the injective mapping property while allowing elements outside A and B to remain unmapped, distinguishing it from full permutations where A = B = S.[10] Graphically, a partial permutation is often depicted as a bipartite graph with partite sets corresponding to two copies of S, say the domain side and range side, where edges connect i \in A to \pi(i) \in B, ensuring no two edges share a vertex.[11] Alternatively, it can be shown in a permutation diagram, similar to full permutations, with horizontal lines for unmatched elements in A or B to highlight the partial nature of the matching.[12] In matrix form, a partial permutation is represented by a partial permutation matrix, an n \times n (0,1)-matrix with at most one 1 in each row and each column, where the positions of the 1s indicate the bijection: a 1 at entry (i, j) means \pi(i) = j.[13] This differs from a full permutation matrix, which has exactly one 1 per row and column, by permitting zero rows and columns for unmatched elements.[14] For example, consider S = \{1,2,3,4\} and \pi(1)=3, \pi(2)=4; the corresponding matrix is \begin{pmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} with 1s at positions (1,3) and (2,4), and 0s elsewhere.[15] This bijection and matrix representations facilitate algebraic manipulations, such as composition of partial permutations via matrix multiplication (adjusted for partial domains), and are implemented in software systems like GAP for computational group theory applications.[8]Sequence Representation
A partial permutation can be represented in sequence form as an ordered tuple (a_1, a_2, \dots, a_k) consisting of k distinct elements from the finite set S = \{1, 2, \dots, n\} with k \leq n, where this sequence implies a bijection \pi: \{1, 2, \dots, k\} \to \{a_1, a_2, \dots, a_k\} defined by \pi(i) = a_i for each i \in \{1, 2, \dots, k\}.[16] This view treats the positions in the sequence as an ordered domain, mapping consecutively from 1 to k, while the values a_i form the corresponding image subset.[17] For instance, given S = \{1, 2, 3\}, the sequence (2, 1) represents the partial permutation where \pi(1) = 2 and \pi(2) = 1, leaving 3 unmapped.[16] This representation highlights the injective nature of the mapping, ensuring no repetitions in the sequence, which aligns with the total number of such partial permutations being P(n, k) = n! / (n - k)!.[17] To convert a general bijection representation—where the domain is an arbitrary subset D \subseteq S of size k—to this sequence form, one orders the elements of D in increasing natural order (or another fixed ordering) to relabel them as 1 through k, then lists the corresponding images in that sequence.[18] This process facilitates systematic enumeration and generation of partial permutations, as sequences lend themselves to lexicographic ordering or recursive construction algorithms for listing all possibilities without duplication.[16] However, this sequence representation assumes an implicitly ordered domain as the initial segment \{1, 2, \dots, k\}, making it less flexible for cases where the domain subset requires preservation of its original structure or non-consecutive labeling, in contrast to the more general bijection view that directly specifies arbitrary subsets.[18]Enumeration
Counting Formulas
The number of partial permutations of order k (i.e., with |\operatorname{dom}(p)| = |\operatorname{ran}(p)| = k) on an n-element set is\binom{n}{k}^2 k!.
This counts the ways to choose the domain subset in \binom{n}{k} ways, the range subset in \binom{n}{k} ways, and then k! bijections between them. Note that \binom{n}{k}^2 k! = \binom{n}{k} P(n,k), where P(n,k) = \frac{n!}{(n-k)!} is the falling factorial, corresponding to fixing the domain subset and counting injections to the range.[2] The total number of partial permutations on the set = \{1, 2, \dots, n\} is then
\sum_{k=0}^n \binom{n}{k}^2 k!.
This sum includes the case k=0, corresponding to the unique empty partial permutation.[19] For example, with n=3, the values are 1 (k=0), 9 (k=1), 18 (k=2), 6 (k=3), for a total of 34.[19]
This counting aligns with the bijection representation of partial permutations.
Generating Functions and Asymptotics
For fixed n, the exponential generating function in the order k for the number of k-partial permutations is\sum_{k=0}^n \binom{n}{k}^2 k! \frac{x^k}{k!} = \sum_{k=0}^n \binom{n}{k}^2 x^k = {}_2F_1(-n, -n; 1; x),
where {}_2F_1 is the Gaussian hypergeometric function. This follows from the known generating function for squares of binomial coefficients. The bivariate exponential generating function enumerating partial permutations over all n and k is
\sum_{n,k \geq 0} \binom{n}{k}^2 k! \frac{x^n}{n!} \frac{y^k}{k!} = \sum_{n \geq 0} \frac{x^n}{n!} \sum_{k=0}^n \binom{n}{k}^2 y^k.
The inner sum is the hypergeometric function as above, and no simpler closed form is standard. The total number of partial permutations on n elements, a_n = \sum_{k=0}^n \binom{n}{k}^2 k! (sequence A002720 in OEIS), has a more complex asymptotic expansion for large n. The sum is dominated by terms where k ≈ n - √n, and detailed analysis requires advanced methods like the saddle-point approximation; the leading behavior grows faster than n! but subexponentially relative to double factorials or similar structures.[19]