Partial permutation
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.
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 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. The seven partial permutations on two items are
The number of partial permutations on n items, for n = 0, 1, 2, ..., is given by the integer sequence
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:
...
Wikipedia