chỉnh hợp chập k của n

From Wikipedia, the miễn phí encyclopedia

Bạn đang xem: chỉnh hợp chập k của n

In combinatorial mathematics, a partial permutation, or sequence without repetition, on a finite phối 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 lớn V. Equivalently, it is a partial function on S that can be extended to lớn a permutation.^[1][2]

Representation[edit]

It is common to lớn consider the case when the phối S is simply the phối {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 lớn and the remaining ones of which are a special "hole" symbol ◊. In this formulation, the tên miền U of the partial permutation consists of the positions in the string that tự not contain a hole, and each such position is mapped to lớn the number in that position. For instance, the string "1 ◊ 2" would represent the partial permutation that maps 1 to lớn itself and maps 3 to lớn 2.^[3] The seven partial permutations on two items are

◊◊, ◊1, ◊2, 1◊, 2◊, 12, 21.

Combinatorial enumeration[edit]

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

Xem thêm: tác dụng của biện pháp liệt kê

in which the ith term counts the number of partial permutations with tư vấn 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:

1. partial permutations where the final elements of each phối are omitted:
2. partial permutations where the final elements of each phối map to lớn each other.
3. partial permutations where the final element of the first phối is included, but does not map to lớn the final element of the second set
4. partial permutations where the final element of the second phối is included, but does not map to lớn the final element of the first set
5. , the partial permutations included in both counts 3 and 4, those permutations where the final elements of both sets are included, but tự not map to lớn each other.

Restricted partial permutations[edit]

Some authors restrict partial permutations sánh that either the domain^[4] or the range^[3] of the bijection is forced to lớn consist of the first k items in the phối 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.)

Xem thêm: lời dẫn chương trình văn nghệ

References[edit]