조합론적 수학(combinatorial mathematics)에서, 유한 집합(finite set) S에 대한 부분 순열, 또는 반복없이 수열은 S의 지정된 두 부분집합(subset) 사이의 전단사(bijection)입니다. 즉, 그것은 같은 크기의 두 부분집합 U와 V에 의해 정의되고, U에서 V로의 일-대-일 매핑입니다. 동등하게, 그것은 순열(permutation)로 확장될 수 있는 S에 대한 부분 함수(partial function)입니다.
Representation
집합 S가 단순히 처음 n 정수의 집합 {1, 2, ..., n}인 경우를 고려하는 것이 공통적입니다. 이 경우에서, 부분 순열은 n 기호의 문자열(string)로 나타낼 수 있으며, 그 중 일부는 1에서 \(\displaystyle n\)로의 범위에서 고유한 숫자이고
그것의 남아있는 것은 특수 "구멍" 기호 ◊입니다. 이 공식에서, 부분 순열의 도메인(domain) U는 구멍을 포함하지 않는 문자열에서 위치로 구성되고, 각 그러한 위치는 해당 위치에서 숫자에 매핑됩니다. 예를 들어, 문자열 "1 ◊ 2"는 1을 자신에 매핑하고 3을 2에 매핑하는 부분 순열을 나타냅니다. 두 항목에 대한 7개의 부분 순열은 다음과 같습니다:
\(\quad\)◊◊, ◊1, ◊2, 1◊, 2◊, 12, 21.
Combinatorial enumeration
n 항목, n = 0, 1, 2, ...에 대해 부분 순열의 숫자는 정수 수열(integer sequence)에 의해 제공됩니다:
여기서 수열에서 n번째 하옥은 합계 공식에 의해 제공됩니다:
\(\quad\displaystyle \sum_{i=0}^n i!\binom{n}{i}^2\)
이것에서 i번째 항은 크기 i의 지원을 갖는 부분 순열의 숫자, 즉, i 비-구멍 엔트리를 갖는 부분 순열의 숫자를 셉니다. 대안적으로, 그것은 다음 재귀 관계(recurrence relation)에 의해 계산될 수 있습니다:
\(\quad\displaystyle P(n) = 2nP(n-1) - (n-1)^2 P(n-2).\)
이것은 다음처럼 결정됩니다:
- \(\displaystyle P(n-1)\) 부분 순열 여기서 각 집합의 마지막 원소는 생략됩니다:
- \(\displaystyle P(n-1)\) 부분 순열 여기서 각 집합의 마지막 원소는 서로 매핑됩니다.
- \(\displaystyle (n-1)P(n-1)\) 부분 순열 여기서 첫 번째 집합의 마지막 원소는 포함되지만, 두 번째 집합의 마지막 원소에 매핑되지 않습니다.
- \(\displaystyle (n-1)P(n-1)\) 부분 순열 여기서 두 번째 집합의 마지막 원소는 포함되지만, 첫 번째 집합의 마지막 원소에 매핑되지 않습니다.
- \(\displaystyle -(n-1)^2P(n-2)\), 단계 3과 4 둘 다에 포함된 부분 순열, 그들 순열 여기서 두 집합의 마지막 원소는 포함되지만, 서로에 매핑되지 않습니다.
Restricted partial permutations
일부 저자는 부분 순열을 제한하여 전단사의 도메인 또는 치역이 일부 k에 대해 순열되는 n 항목 집합에서 첫 번째 k 항목으로 구성되도록 강제합니다. 전자의 경우에서, n-집합에서 길이 k의 부분 순열은 반복없이 n-집합에서 k 항의 수열일 뿐입니다. (초등 조합론에서, 이들 대상은 때때로 n-집합의 "k-순열"이라고 혼란스럽게 불립니다.)
References
- 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 0685635.
- 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.
- 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.
- Burstein, Alexander; Lankham, Isaiah (2010), "Restricted patience sorting and barred pattern avoidance", Permutation patterns, London Math. Soc. Lecture Note Ser., vol. 376, Cambridge: Cambridge Univ. Press, pp. 233–257, arXiv:math/0512122, doi:10.1017/CBO9780511902499.013, MR 2732833.
