• Source: 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.




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


{\displaystyle 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.
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





∑

i
=
0


n


i
!




(


n
i


)




2




{\displaystyle \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
)
=
2
n
P
(
n
−
1
)
−
(
n
−
1

)

2


P
(
n
−
2
)
.


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


This is determined as follows:




P
(
n
−
1
)


{\displaystyle P(n-1)}

partial permutations where the final elements of each set are omitted:




P
(
n
−
1
)


{\displaystyle P(n-1)}

partial permutations where the final elements of each set map to each other.




(
n
−
1
)
P
(
n
−
1
)


{\displaystyle (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
)


{\displaystyle (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
)


{\displaystyle -(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
or the range 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

Kata Kunci Pencarian:

• Statistika
• Variabel acak
• Ilmu aktuaria
• Statistika matematika
• Daftar bilangan prima
• Defisiensi fumarase
• Model generatif
• Efek pengacau
• Eksperimen semu
• Akhmaloka
• Partial permutation
• Permutation
• Sudoku solving algorithms
• Levi-Civita symbol
• Eight queens puzzle
• Monad (functional programming)
• Permutation test
• Random permutation statistics
• Random forest
• Pseudorandom permutation