Partial permutation

From Wikipedia, the free encyclopedia

In combinatorial mathematics, a partial permutation 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]

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]

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

  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 685635 .
  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 .
  3. ↑ 3.0 3.1 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. 376, Cambridge: Cambridge Univ. Press, pp. 233–257, doi:10.1017/CBO9780511902499.013, MR 2732833 .


This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.