# 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.^{[1]}^{[2]}

## Contents

## 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 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

where the *n*th item in the sequence is given by the summation formula

in which the *i*th 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:

- partial permutations where the final elements of each set are omitted:
- partial permutations where the final elements of each set map to each other.
- partial permutations where the final element of the first set is included, but does not map to the final element of the second set
- partial permutations where the final element of the second set is included, but does not map to the final element of the first set
- , 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.)