Partial permutation

Last updated July 24, 2023

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

It is common to consider the case when the set S is simply the set {1, 2, ..., n} of the first n 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 $n$ 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

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

\sum _{i=0}^{n}i!{\binom {n}{i}}^{2}

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

P(n)=2nP(n-1)-(n-1)^{2}P(n-2).

This is determined as follows:

$P(n-1)$ partial permutations where the final elements of each set are omitted:
$P(n-1)$ partial permutations where the final elements of each set map to each other.
$(n-1)P(n-1)$ partial permutations where the final element of the first set is included, but does not map to the final element of the second set
$(n-1)P(n-1)$ partial permutations where the final element of the second set is included, but does not map to the final element of the first set
$-(n-1)^{2}P(n-2)$ , 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

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.)

Related Research Articles

In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter. For example, given three fruits, say an apple, an orange and a pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally, a k-combination of a set S is a subset of k distinct elements of S. So, two combinations are identical if and only if each combination has the same members. If the set has n elements, the number of k-combinations, denoted by $or, is equal to the binomial coefficient$

In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order of an ordered set.

In combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for deriving the generating functions of discrete structures, which allows one to not merely count these structures but give bijective proofs involving them. Examples of combinatorial species are graphs, permutations, trees, and so on; each of these has an associated generating function which counts how many structures there are of a certain size. One goal of species theory is to be able to analyse complicated structures by describing them in terms of transformations and combinations of simpler structures. These operations correspond to equivalent manipulations of generating functions, so producing such functions for complicated structures is much easier than with other methods. The theory was introduced, carefully elaborated and applied by Canadian researchers around André Joyal.

In combinatorial mathematics, the Bell numbers count the possible partitions of a set. These numbers have been studied by mathematicians since the 19th century, and their roots go back to medieval Japan. In an example of Stigler's law of eponymy, they are named after Eric Temple Bell, who wrote about them in the 1930s.

Counting is the process of determining the number of elements of a finite set of objects; that is, determining the size of a set. The traditional way of counting consists of continually increasing a counter by a unit for every element of the set, in some order, while marking those elements to avoid visiting the same element more than once, until no unmarked elements are left; if the counter was set to one after the first object, the value after visiting the final object gives the desired number of elements. The related term enumeration refers to uniquely identifying the elements of a finite (combinatorial) set or infinite set by assigning a number to each element.

Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous. In contrast to real numbers that have the property of varying "smoothly", the objects studied in discrete mathematics – such as integers, graphs, and statements in logic – do not vary smoothly in this way, but have distinct, separated values. Discrete mathematics, therefore, excludes topics in "continuous mathematics" such as calculus and analysis.

In mathematics, the term combinatorial proof is often used to mean either of two types of mathematical proof:

In mathematics, particularly in combinatorics, given a family of sets, here called a collection C, a transversal (also called a cross-section) is a set containing exactly one element from each member of the collection. When the sets of the collection are mutually disjoint, each element of the transversal corresponds to exactly one member of C (the set it is a member of). If the original sets are not disjoint, there are two possibilities for the definition of a transversal:

In combinatorics, bijective proof is a proof technique for proving that two sets have equally many elements, or that the sets in two combinatorial classes have equal size, by finding a bijective function that maps one set one-to-one onto the other. This technique can be useful as a way of finding a formula for the number of elements of certain sets, by corresponding them with other sets that are easier to count. Additionally, the nature of the bijection itself often provides powerful insights into each or both of the sets.

In combinatorial mathematics, a de Bruijn sequence of order n on a size-k alphabet A is a cyclic sequence in which every possible length-n string on A occurs exactly once as a substring (i.e., as a contiguous subsequence). Such a sequence is denoted by B(k, n) and has length kⁿ, which is also the number of distinct strings of length n on A. Each of these distinct strings, when taken as a substring of B(k, n), must start at a different position, because substrings starting at the same position are not distinct. Therefore, B(k, n) must have at leastkⁿ symbols. And since B(k, n) has exactlykⁿ symbols, De Bruijn sequences are optimally short with respect to the property of containing every string of length n at least once.

209 is the natural number following 208 and preceding 210.

<span class="mw-page-title-main">Ordered Bell number</span> Number of weak orderings

In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the number of weak orderings on a set of $elements. Weak orderings arrange their elements into a sequence allowing ties, such as might arise as the outcome of a horse race). Starting from, these numbers are$

In the mathematical study of permutations and permutation patterns, a superpattern or universal permutation is a permutation that contains all of the patterns of a given length. More specifically, a k-superpattern contains all possible patterns of length k.

In computer science and the study of combinatorics on words, a partial word is a string that may contain a number of "do not know" or "do not care" symbols i.e. placeholders in the string where the symbol value is not known or not specified. More formally, a partial word is a partial function $where is some finite alphabet. If u (k) is not defined for some then the unknown element at place k in the string is called a "hole". In regular expressions (following the POSIX standard) a hole is represented by the metacharacter ".". For example, aab.ab.b is a partial word of length 8 over the alphabet A ={a, b} in which the fourth and seventh characters are holes.$

In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the permutation to the digit sequence 123...; for instance the digit sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way, then π is said to contain σ as a pattern if some subsequence of the digits of π has the same relative order as all of the digits of σ.

In combinatorics, the Schröder–Hipparchus numbers form an integer sequence that can be used to count the number of plane trees with a given set of leaves, the number of ways of inserting parentheses into a sequence, and the number of ways of dissecting a convex polygon into smaller polygons by inserting diagonals. These numbers begin

In mathematics, the telephone numbers or the involution numbers form a sequence of integers that count the ways $n$ people can be connected by person-to-person telephone calls. These numbers also describe the number of matchings of a complete graph on $n$ vertices, the number of permutations on $n$ elements that are involutions, the sum of absolute values of coefficients of the Hermite polynomials, the number of standard Young tableaux with $n$ cells, and the sum of the degrees of the irreducible representations of the symmetric group. Involution numbers were first studied in 1800 by Heinrich August Rothe, who gave a recurrence equation by which they may be calculated, giving the values

In mathematics and computer science, a stack-sortable permutation is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. The stack-sortable permutations are exactly the permutations that do not contain the permutation pattern 231; they are counted by the Catalan numbers, and may be placed in bijection with many other combinatorial objects with the same counting function including Dyck paths and binary trees.

In the mathematical study of combinatorics on words, a parameter word is a string over a given alphabet having some number of wildcard characters. The set of strings matching a given parameter word is called a parameter set or combinatorial cube. Parameter words can be composed, to produce smaller subcubes of a given combinatorial cube. They have applications in Ramsey theory and in computer science in the detection of duplicate code.

The affine symmetric groups are a family of mathematical structures that describe the symmetries of the number line and the regular triangular tiling of the plane, and related higher-dimensional objects. Each one is an infinite extension of a finite symmetric group, the group of permutations (rearrangements) of a finite set. In addition to their geometric description, the affine symmetric groups may be defined as collections of permutations of the integers that are periodic in a certain sense, or in purely algebraic terms as a group with certain generators and relations. They are studied as part of the fields of combinatorics and representation theory.

References

↑ Straubing, Howard (1983), "A combinatorial proof of the Cayley-Hamilton theorem", Discrete Mathematics, 43 (2–3): 273–279, doi: 10.1016/0012-365X(83)90164-4 , MR 0685635 .
↑ Ku, C. Y.; Leader, I. (2006), "An Erdős-Ko-Rado theorem for partial permutations", Discrete Mathematics , 306 (1): 74–86, doi: 10.1016/j.disc.2005.11.007 , MR 2202076 .
1 2 Claesson, Anders; Jelínek, Vít; Jelínková, Eva; Kitaev, Sergey (2011), "Pattern avoidance in partial permutations", Electronic Journal of Combinatorics, 18 (1): Paper 25, 41, MR 2770130 .
↑ Burstein, Alexander; Lankham, Isaiah (2010), "Restricted patience sorting and barred pattern avoidance", Permutation patterns, London Math. Soc. Lecture Note Ser., vol. 376, Cambridge: Cambridge Univ. Press, pp. 233–257, arXiv: math/0512122 , doi:10.1017/CBO9780511902499.013, MR 2732833 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Straubing, Howard (1983), "A combinatorial proof of the Cayley-Hamilton theorem", Discrete Mathematics, 43 (2–3): 273–279, doi: 10.1016/0012-365X(83)90164-4 , MR 0685635 .

[2] Ku, C. Y.; Leader, I. (2006), "An Erdős-Ko-Rado theorem for partial permutations", Discrete Mathematics , 306 (1): 74–86, doi: 10.1016/j.disc.2005.11.007 , MR 2202076 .

[cjjk-3] 1 2 Claesson, Anders; Jelínek, Vít; Jelínková, Eva; Kitaev, Sergey (2011), "Pattern avoidance in partial permutations", Electronic Journal of Combinatorics, 18 (1): Paper 25, 41, MR 2770130 .

[4] Burstein, Alexander; Lankham, Isaiah (2010), "Restricted patience sorting and barred pattern avoidance", Permutation patterns, London Math. Soc. Lecture Note Ser., vol. 376, Cambridge: Cambridge Univ. Press, pp. 233–257, arXiv: math/0512122 , doi:10.1017/CBO9780511902499.013, MR 2732833 .

[1]

[2]

[3]

[4]