Hubbry Logo
search
logo
Partial permutation avatar
Partial permutation
Partial permutation
current hub
P

Partial permutation

logo
Community Hub0 Subscribers
Read side by side
Partial permutation
View on Wikipedia
from Wikipedia

In combinatorial mathematics, a partial permutation, or sequence without repetition, on a finite set S is a bijection between two specified subsets of S. That is, 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.[1][2]

Representation

[edit]

It is common to consider the case when the set S is simply the set {1, 2, ..., n} of the first n positive integers. In this case, a partial permutation may be represented by a string of n symbols, some of which are distinct numbers in the range from 1 to and the remaining ones of which are a special "hole" symbol ◊. In this formulation, the domain U of the partial permutation consists of the positions in the string that do not contain a hole, and each such position is mapped to the number in that position. For instance, the string "1 ◊ 2" would represent the partial permutation that maps 1 to itself and maps 3 to 2.[3] The seven partial permutations on two items are

◊◊, ◊1, ◊2, 1◊, 2◊, 12, 21.

Combinatorial enumeration

[edit]

The number of partial permutations on n items, for n = 0, 1, 2, ..., is given by the integer sequence

1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114, 234662231, ... (sequence A002720 in the OEIS)

where the nth item in the sequence is given by the summation formula

in which the ith term counts the number of partial permutations with support of size i, that is, the number of partial permutations with i non-hole entries. Alternatively, it can be computed by a recurrence relation

This is determined as follows:

  1. partial permutations where the final elements of each set are omitted:
  2. partial permutations where the final elements of each set map to each other.
  3. partial permutations where the final element of the first set is included, but does not map to the final element of the second set
  4. partial permutations where the final element of the second set is included, but does not map to the final element of the first set
  5. , the partial permutations included in both counts 3 and 4, those permutations where the final elements of both sets are included, but do not map to each other.

Restricted partial permutations

[edit]

Some authors restrict partial permutations so that either the domain[4] or the range[3] of the bijection is forced to consist of the first k items in the set of n items being permuted, for some k. In the former case, a partial permutation of length k from an n-set is just a sequence of k terms from the n-set without repetition. (In elementary combinatorics, these objects are sometimes confusingly called "k-permutations" of the n-set.)

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Partial permutation

View on Grokipedia
from Grokipedia
A partial permutation on a finite set XX is a bijection between two subsets of XX of equal cardinality, generalizing the notion of a full permutation, which is a bijection from XX to itself.[1] The domain and range of such a bijection are denoted dom⁡(p)\operatorname{dom}(p) and ran⁡(p)\operatorname{ran}(p), respectively, and may be empty or proper subsets.[1] In combinatorics, partial permutations are enumerated by considering the size kk of the subsets involved; the total number of partial permutations on a set of nn elements is ∑k=0n(nk)2k!\sum_{k=0}^{n} \binom{n}{k}^2 k!, which counts the ways to choose the domain and range subsets of size kk and then pair them bijectively.[2] Special cases include monotonic partial permutations, numbering (2nn)\binom{2n}{n}, and decreasing partial permutations, numbering the (n+1)(n+1)-th Bell number Bn+1B_{n+1}.[2] Composition of partial permutations is defined where possible, as $ (p \circ q)(x) = p(q(x)) $ for xx 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 XX.[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 SS is defined as a bijection π:A→B\pi: A \to B, where AA and BB are subsets of SS such that ∣A∣=∣B∣=k≤∣S∣|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 kk elements from SS to itself without requiring full coverage of SS.[4] The domain of π\pi, denoted \dom(π)\dom(\pi), is the subset A⊆SA \subseteq S on which π\pi is defined, while the range, denoted \ran(π)\ran(\pi), is the subset B⊆SB \subseteq S that serves as the image of AA under π\pi.[1] The size of the partial permutation is given by k=∣\dom(π)∣=∣\ran(π)∣k = |\dom(\pi)| = |\ran(\pi)|, representing the number of elements actively mapped by π\pi.[4] For instance, consider S={1,2,3}S = \{1, 2, 3\} and the mapping π\pi that sends 11 to 33 while leaving 22 and 33 undefined in the domain; here, \dom(π)={1}\dom(\pi) = \{1\}, \ran(π)={3}\ran(\pi) = \{3\}, and the size is k=1k=1.[1] Partial permutations are frequently studied in the context of the set [n]={1,2,…,n}[n] = \{1, 2, \dots, n\}, where S=[n]S = [n]. Unlike a general injection from a subset of SS into SS, 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(π)=\ran(π)=S\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 SS of size nn is equivalent to an nn-partial permutation on SS, where the domain and range both coincide with SS.[5] Note that in some combinatorial contexts, particularly in permutation pattern avoidance, "partial permutations" alternatively refer to injections from [k][k] to [n][n], which are ordered selections of kk distinct elements from [n][n] (counted by P(n,k)=n!(n−k)!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 XX is defined as a bijection π:\dom(π)→\ran(π)\pi: \dom(\pi) \to \ran(\pi), where \dom(π)\dom(\pi) and \ran(π)\ran(\pi) are subsets of XX with equal cardinality k=∣\dom(π)∣=∣\ran(π)∣k = |\dom(\pi)| = |\ran(\pi)|.[1][4] By this definition, π\pi is injective on its domain, meaning distinct elements in \dom(π)\dom(\pi) map to distinct elements in \ran(π)\ran(\pi), and surjective onto its range, meaning every element in \ran(π)\ran(\pi) is the image of exactly one element in \dom(π)\dom(\pi).[1][4] The support of a partial permutation π\pi, denoted \supp(π)\supp(\pi), is the union \dom(π)∪\ran(π)\dom(\pi) \cup \ran(\pi), which captures all elements of XX involved in the mapping.[7] The size of the support satisfies k≤∣\supp(π)∣≤2kk \leq |\supp(\pi)| \leq 2k, since ∣\supp(π)∣=2k−∣\dom(π)∩\ran(π)∣|\supp(\pi)| = 2k - |\dom(\pi) \cap \ran(\pi)|, with equality to kk occurring when \dom(π)=\ran(π)\dom(\pi) = \ran(\pi).[4] For a partial permutation of size kk on the set [n]={1,2,…,n}[n] = \{1, 2, \dots, n\} with n≥2kn \geq 2k, the possible supports are subsets of [n][n] of size between kk and 2k2k, chosen such that there exist subsets A,B⊆SA, B \subseteq S (not necessarily disjoint) with ∣A∣=∣B∣=k|A| = |B| = k and A∪B=SA \cup B = S. For example, on [5][5] with k=2k=2, a possible support is {1,2,3}\{1,2,3\}, where \dom(π)={1,2}\dom(\pi) = \{1,2\} and \ran(π)={2,3}\ran(\pi) = \{2,3\}, allowing mappings like π(1)=2\pi(1)=2, π(2)=3\pi(2)=3.[4] Fixed points of π\pi are elements x∈\dom(π)∩\ran(π)x \in \dom(\pi) \cap \ran(\pi) such that π(x)=x\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∈\dom(π)∩\ran(π)∣π(x)=x}\{x \in \dom(\pi) \cap \ran(\pi) \mid \pi(x) = x\}. In the identity partial permutation on a subset A⊆XA \subseteq X with \dom(π)=\ran(π)=A\dom(\pi) = \ran(\pi) = A, every element of AA 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 π:A→B\pi: A \to B with A,B⊆XA, B \subseteq X and ∣A∣=∣B∣=k<∣X∣|A| = |B| = k < |X|, there exists a permutation σ\sigma of XX such that σ\sigma extends π\pi, meaning A⊆\dom(σ)A \subseteq \dom(\sigma) and σ(a)=π(a)\sigma(a) = \pi(a) for all a∈Aa \in A. This extension is not unique in general but always exists, for example by choosing any bijection from X∖\dom(π)X \setminus \dom(\pi) to X∖\ran(π)X \setminus \ran(\pi).[1] Conversely, any injective mapping f:S→Tf: S \to T between finite subsets S,T⊆XS, T \subseteq X with ∣S∣=∣T∣|S| = |T| uniquely defines a partial permutation with \dom(f)=S\dom(f) = S and \ran(f)=T\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 π1\pi_1 and π2\pi_2 on a set XX. The composition π1∘π2\pi_1 \circ \pi_2 is defined on the subset of \dom(π1)\dom(\pi_1) where π1(x)∈\dom(π2)\pi_1(x) \in \dom(\pi_2), with (π1∘π2)(x)=π2(π1(x))(\pi_1 \circ \pi_2)(x) = \pi_2(\pi_1(x)) for such xx. Thus, \dom(π1∘π2)=π1−1(\dom(π2)∩\ran(π1))\dom(\pi_1 \circ \pi_2) = \pi_1^{-1}(\dom(\pi_2) \cap \ran(\pi_1)) and \ran(π1∘π2)=π2(\dom(π2)∩\ran(π1))\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 π1\pi_1 and π2\pi_2.[8] If \ran(π1)∩\dom(π2)=∅\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(π1)∩\dom(π2)=∅\dom(\pi_1) \cap \dom(\pi_2) = \emptyset and \ran(π1)∩\ran(π2)=∅\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 π−1\pi^{-1} is the unique partial permutation satisfying π∘π−1=\id\ran(π)\pi \circ \pi^{-1} = \id_{\ran(\pi)} and π−1∘π=\id\dom(π)\pi^{-1} \circ \pi = \id_{\dom(\pi)}, where \id\id denotes the identity on the respective subsets. Here, \dom(π−1)=\ran(π)\dom(\pi^{-1}) = \ran(\pi) and \ran(π−1)=\dom(π)\ran(\pi^{-1}) = \dom(\pi), with π−1(y)=x\pi^{-1}(y) = x if π(x)=y\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 kk on a set XX with ∣X∣>k|X| > k, an extension to rank k+1k+1 is obtained by selecting an element i∈X∖\dom(π)i \in X \setminus \dom(\pi) for the domain and j∈X∖\ran(π)j \in X \setminus \ran(\pi) for the range, then adding the mapping i↦ji \mapsto j to π\pi. The resulting function remains a bijection between the enlarged subsets. This process can be repeated until the rank reaches ∣X∣|X|, potentially yielding a full permutation. For example, consider X={1,2,3,4}X = \{1,2,3,4\} and π1:1↦2\pi_1: 1 \mapsto 2, a rank-1 partial permutation. Composing with π2:2↦3\pi_2: 2 \mapsto 3 (rank 1, with overlap) gives π1∘π2:1↦3\pi_1 \circ \pi_2: 1 \mapsto 3 (rank 1). If instead π3:3↦4\pi_3: 3 \mapsto 4 (disjoint support), their disjoint union is 1↦2,3↦41 \mapsto 2, 3 \mapsto 4 (rank 2). Extending π1\pi_1 by adding 3↦43 \mapsto 4 yields the same rank-2 partial permutation. In non-disjoint cases, such as composing π1\pi_1 with π4:2↦1\pi_4: 2 \mapsto 1 (overlap but cycle), the result is the empty partial permutation since \ran(π1)∩\dom(π4)={2}\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 XX with ∣X∣=n|X| = n, denoted InI_n, forms an inverse monoid under the above composition operation, including the identity partial permutation (full bijection on XX) 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 ∣In∣=∑k=0n(nk)2k!|I_n| = \sum_{k=0}^n \binom{n}{k}^2 k!.[9]

Representations

Bijection Representation

A partial permutation can be viewed as a bijection π:A→B\pi: A \to B, where A,B⊆SA, B \subseteq S for a finite set S={1,2,…,n}S = \{1, 2, \dots, n\} and ∣A∣=∣B∣|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 AA and BB to remain unmapped, distinguishing it from full permutations where A=B=SA = B = S.[10] Graphically, a partial permutation is often depicted as a bipartite graph with partite sets corresponding to two copies of SS, say the domain side and range side, where edges connect i∈Ai \in A to π(i)∈B\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 AA or BB to highlight the partial nature of the matching.[12] In matrix form, a partial permutation is represented by a partial permutation matrix, an n×nn \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)(i, j) means π(i)=j\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}S = \{1,2,3,4\} and π(1)=3\pi(1)=3, π(2)=4\pi(2)=4; the corresponding matrix is
(0010000100000000) \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 (a1,a2,…,ak)(a_1, a_2, \dots, a_k) consisting of kk distinct elements from the finite set S={1,2,…,n}S = \{1, 2, \dots, n\} with k≤nk \leq n, where this sequence implies a bijection π:{1,2,…,k}→{a1,a2,…,ak}\pi: \{1, 2, \dots, k\} \to \{a_1, a_2, \dots, a_k\} defined by π(i)=ai\pi(i) = a_i for each i∈{1,2,…,k}i \in \{1, 2, \dots, k\}.[16] This view treats the positions in the sequence as an ordered domain, mapping consecutively from 1 to kk, while the values aia_i form the corresponding image subset.[17] For instance, given S={1,2,3}S = \{1, 2, 3\}, the sequence (2,1)(2, 1) represents the partial permutation where π(1)=2\pi(1) = 2 and π(2)=1\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)!P(n, k) = n! / (n - k)!.[17] To convert a general bijection representation—where the domain is an arbitrary subset D⊆SD \subseteq S of size kk—to this sequence form, one orders the elements of DD in increasing natural order (or another fixed ordering) to relabel them as 1 through kk, 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,…,k}\{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
(nk)2k!. \binom{n}{k}^2 k!.
This counts the ways to choose the domain subset in (nk)\binom{n}{k} ways, the range subset in (nk)\binom{n}{k} ways, and then k! bijections between them. Note that (nk)2k!=(nk)P(n,k)\binom{n}{k}^2 k! = \binom{n}{k} P(n,k), where P(n,k)=n!(n−k)!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 [n]={1,2,…,n}[n] = \{1, 2, \dots, n\} is then
∑k=0n(nk)2k!. \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
∑k=0n(nk)2k!xkk!=∑k=0n(nk)2xk=2F1(−n,−n;1;x), \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 2F1{}_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
∑n,k≥0(nk)2k!xnn!ykk!=∑n≥0xnn!∑k=0n(nk)2yk. \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, an=∑k=0n(nk)2k!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]

Applications

In Combinatorics and Probability

Partial permutations play a central role in rook theory, where they model the placement of non-attacking rooks on a chessboard with restricted positions. The rook polynomial of a board enumerates the number of ways to place k non-attacking rooks, which directly corresponds to the number of partial permutations of size k avoiding forbidden positions on the board. This connection was established in the foundational work of Kaplansky and Riordan, who unified various combinatorial counting problems using rook placements to represent partial matchings and permutations with restrictions.[20] The coefficients of the rook polynomial are computed via inclusion-exclusion principles, providing exact counts for these partial permutations by accounting for overplacements on restricted squares.[21] In probabilistic models, random partial permutations arise in matching problems, such as assigning k distinct items to n slots without conflicts. For instance, the probability of fixed points in a random permutation of a k-subset of [n]—where a fixed point occurs if an element maps to itself—can be analyzed using linearity of expectation, yielding an expected number of approximately k/n fixed points for large n. This extends classical derangement probabilities to partial settings, informing models in random allocations and bipartite matchings. The enumeration of partial permutations by cycle structure on their support connects to unsigned Stirling numbers of the first kind. Specifically, the number of partial permutations of [n] with support size k and exactly m cycles equals \binom{n}{k} times the unsigned Stirling number of the first kind c(k, m), which counts the permutations of k elements into m cycles. This relation facilitates the study of cycle distributions in random partial permutations, with applications in analyzing the structure of random injections. A practical example appears in variants of the birthday problem, where partial permutations count the number of collision-free assignments of birthdays to people. For n people and d=365 days, the number of ways to assign distinct birthdays is the falling factorial d^{\underline{n}} = P(d, n), equivalent to the number of partial permutations of size n on d elements, yielding the probability of no shared birthday as P(d, n)/d^n. This framework extends to generalized collision problems in hashing and cryptography.

In Algorithms and Computer Science

In string algorithms, partial permutations facilitate efficient dictionary matching by representing partial bijections between symbol sets, enabling the identification of common subsequences or patterns in multiple texts over a shared alphabet. This approach supports querying whether a set of partial permutations agrees on a subset of symbols, with applications in pattern matching tasks where only partial mappings are known.[4] Maintenance of dynamic partial permutations involves data structures that support insertions and deletions while preserving the bijection properties. One such structure uses O(n · |Σ|) space to handle updates in O(|Σ|) time and queries for agreement in O(n · |Σ| · log |Σ| / 2^{Ω(√log |Σ|)}) time, allowing efficient management of evolving mappings in applications like real-time sequence alignment. For nearly full partial permutations, specialized structures achieve O(poly(|Σ|) · n) space with O(poly(|Σ|)) time for both updates and queries. Representations such as adjacency lists or sorted arrays enable these operations by tracking domain and range sets efficiently.[4] Comparison of partial permutations often relies on lexicographic ordering, where sequences are sorted by comparing domain-range pairs iteratively from the smallest undefined positions. Algorithms for this use domain-range matching to determine agreement or order, achieving O(|Σ|) time per comparison with compact representations like bitvectors for symbol presence. Sorting a set of partial permutations can then proceed via comparison-based methods, such as merge sort adapted for partial bijections, in O(k · |Σ| · log k) time for k permutations.[4] In cryptography, partial permutations underpin energy-efficient encryption schemes for network-coded wireless sensor networks, where only global encoding vectors are permuted to secure transmissions without full message rearrangement, reducing computational overhead while maintaining security against eavesdroppers. In coding theory, partial permutation decoding enhances error correction in linear codes like Reed-Muller or abelian codes by applying sets of automorphisms to shift errors out of information sets, correcting up to s errors with a PD-set of size s+1. This method improves decoding efficiency for t-error-correcting codes by focusing on partial rather than full permutations.[22][23][24] In computational group theory, the GAP software implements partial permutations as injective functions between finite sets of positive integers, supporting operations like composition and inversion for tasks such as analyzing permutation groups or monoids in algebraic computations. These implementations aid in exploring structures like transformation semigroups, where partial permutations model incomplete mappings in group actions.[8]

Variants and Extensions

Restricted Partial Permutations

Restricted partial permutations are injections from a subset of size kk of the domain [n][n] to the codomain [n][n] that avoid specified forbidden domain-range pairs (i,j)(i,j), meaning π(i)≠j\pi(i) \neq j for each such pair. These structures are modeled combinatorially as partial matchings in a bipartite graph with partite sets corresponding to the domain and codomain, where edges represent allowed assignments. Equivalently, they correspond to placements of kk non-attacking rooks on an n×nn \times n board BB whose cells indicate permitted positions, excluding the forbidden ones.[20] The number of restricted partial permutations of size kk, denoted rk(B)r_k(B), is the kk-th rook number of the board BB. These are generated by the rook polynomial
R(B,x)=∑k=0nrk(B)xk, R(B, x) = \sum_{k=0}^n r_k(B) x^k,
which encapsulates the enumeration across all possible sizes and facilitates asymptotic analysis for large nn. For boards with mm forbidden positions, rk(B)r_k(B) approximates the unrestricted falling factorial P(n,k)=n(n−1)⋯(n−k+1)P(n,k) = n(n-1)\cdots(n-k+1) with subtractions for configurations violating restrictions, though exact counts require board-specific adjustments. Enumeration proceeds via rook polynomials, computable by the deletion-involution recursion: for a cell c∈Bc \in B, rk(B)=rk(B∖c)+rk−1(B/c)r_k(B) = r_k(B \setminus c) + r_{k-1}(B / c), where B∖cB \setminus c removes the cell cc, and B/cB / c removes the row and column of cc. Inclusion-exclusion also applies, particularly for sparse restrictions, by overcounting and correcting for intersections of forbidden sets.[21][25][20] A canonical example arises on an n×nn \times n board with certain squares removed to represent forbidden positions; here, rk(B)r_k(B) counts the ways to place kk non-attacking rooks on the surviving board, directly yielding the restricted partial permutations. For a board with mm isolated forbidden squares, the count begins as P(n,k)P(n,k) and subtracts terms for rooks landing on each forbidden square, with higher-order inclusions for multiple overlaps.[20][25] Computing these enumerations connects to matrix permanents: for the 0-1 adjacency matrix AA of BB (with 1s on allowed positions), the full case rn(B)r_n(B) equals per⁡(A)\operatorname{per}(A), the number of perfect matchings avoiding forbiddens. For partial size kk, rk(B)r_k(B) equals the sum of permanents over all k×kk \times k principal submatrices of AA, linking restricted partial permutations to bipartite matching theory.[21][20] The framework for restricted partial permutations originated in rook theory, pioneered by Kaplansky and Riordan in 1946 to enumerate non-attacking rook configurations under positional constraints. This approach underpins variants of the problème des ménages, extending to partial seating arrangements that avoid specific adjacencies modeled as forbidden positions on a circular board.[20][21]

Pattern-Avoiding Partial Permutations

A partial permutation, represented as a sequence of length nn with entries from {0,1,…,n}\{0, 1, \dots, n\} where non-zero entries are distinct and at most one per row and column, avoids a pattern σ∈Sm\sigma \in S_m if there is no increasing sequence of indices i1<i2<⋯<imi_1 < i_2 < \dots < i_m such that the non-zero values πi1,πi2,…,πim\pi_{i_1}, \pi_{i_2}, \dots, \pi_{i_m} are order-isomorphic to σ\sigma (i.e., their relative order matches σ\sigma).[26] This definition focuses on the subsequence formed by the non-hole positions, ignoring the gaps introduced by zeros. The enumeration of pattern-avoiding partial permutations often leverages generating functions based on the induced permutation on the non-hole entries. For avoiding length-2 patterns, such as 12 (no increasing pair of non-zero entries, yielding a decreasing induced permutation), or 21 (no decreasing pair, yielding an increasing induced permutation), the count for partial permutations with exactly kk non-holes is (nk)2\binom{n}{k}^2. This arises from choosing kk positions for the non-holes and kk distinct values, assigning them in strictly decreasing (for 12-avoidance) or increasing (for 21-avoidance) order along the positions.[26] The generating function over kk for fixed nn is ∑k=0n(nk)2xk\sum_{k=0}^n \binom{n}{k}^2 x^k.[26] A representative example is partial permutations avoiding the pattern 132. Here, the induced permutation on the non-hole entries must avoid 132, which is enumerated by the Catalan numbers Ck=1k+1(2kk)C_k = \frac{1}{k+1} \binom{2k}{k}. Thus, for exactly kk non-holes, the number is (nk)2Ck\binom{n}{k}^2 C_k. These counts connect to lattice paths via the standard bijection between 132-avoiding permutations of [k][k] and Dyck paths of semilength kk (non-intersecting lattice paths from (0,0) to (2k,0) with steps (1,1) and (1,-1) staying non-negative), extended by choosing positions and values independently.[26] Extensions consider holes explicitly as gaps in the sequence representation, where pattern avoidance applies solely to the order of non-gap entries, preserving the injection property while allowing arbitrary gap placements. This framework naturally accommodates varying numbers of holes without altering the avoidance condition on the filled subsequence.[26]

References

  1. [PDF] Extending partial permtations
  2. [PDF] Notes on Counting: An Introduction to Enumerative Combinatorics
  3. GAP (ref) - Chapter 54: Partial permutations
  4. [PDF] Partial Permutations Comparison, Maintenance and Applications
  5. [PDF] pattern avoidance in partial permutations - SPIDER-V
  6. [PDF] arXiv:2207.10252v1 [math.CO] 21 Jul 2022
  7. Permutation -- from Wolfram MathWorld
  8. [PDF] On the Algebraic Combinatorics of Injections
  9. Chance Combinatorics: The Theory that History Forgot
  10. Why are permutations (nPr) called variations in non-English ...
  11. [PDF] Symmetric Group Gauge Theories and Simple Gauge/String Dualities
  12. GAP (ref) - Chapter 54: Partial permutations
  13. [PDF] 1 Inverse semigroups and orders
  14. On the Extension Problem for Partial Permutations - jstor
  15. [PDF] arXiv:2107.05024v1 [math.CO] 11 Jul 2021
  16. Permutation represented as a bipartite graph. - ResearchGate
  17. [PDF] Pattern avoidance in partial permutations (extended ... - HAL Inria
  18. [PDF] Filtered RSK and matrix Schubert varieties
  19. A partial permutation matrix representing a particular selection and...
  20. GAP (ref) - Chapter 42: Permutations
  21. [PDF] LECTURE 2 Counting Techniques §2.3 - UMD MATH
  22. [PDF] arXiv:2503.17552v1 [math.CO] 21 Mar 2025
  23. 1.3 Combinations and Permutations
  24. Counting Permutations | Brilliant Math & Science Wiki
  25. A000522 - OEIS
  26. [PDF] Combinatorics: The Art of Counting - Michigan State University
  27. [PDF] AC.pdf - Analytic Combinatorics
  28. The problem of the rooks and its applications - Project Euclid
  29. [PDF] Rook Theory Notes - UCSD Math
  30. [PDF] 1 S.-D. Poisson Researches into the Probabilities of Judgements in ...
  31. Energy Efficient Partial Permutation Encryption on Network Coded ...
  32. Partial permutation decoding for codes from finite planes
  33. [PDF] Improved partial permutation decoding for Reed-Muller codes
  34. [PDF] Notes on Rook Polynomials F. Butler J. Haglund J. B. Remmel
  35. [PDF] Pattern Avoidance in the Rook Monoid
User Avatar
No comments yet.