부분순열

결합 수학에서, 유한 집합 S에 대한 부분 순열 또는 반복이 없는 시퀀스는 S의 두 지정된 하위 집합 사이의 편향이다.즉, 크기가 같은 두 서브셋 U와 V, 그리고 U에서 V로 일대일 매핑으로 정의된다.동등하게, 순열로 확장할 수 있는 S의 부분함수다.^[1][2]

표현

집합 S가 단순히 첫 번째 n 정수의 집합 {1, 2, ..., n}인 경우를 고려하는 것이 일반적이다.이 경우 부분 순열은 n 기호의 문자열로 나타낼 수 있으며, 그 중 일부는 1에서$n$까지의 범위에서 구별되는 숫자로, 나머지$$ 하나는 특별한 "$구멍$" 기호 ◊이다.이 공식에서 부분 순열의 도메인 U는 구멍을 포함하지 않는 문자열 내의 위치로 구성되며, 각각의 그러한 위치는 그 위치의 숫자에 매핑된다.예를 들어, "1 2 2" 문자열은 1을 자체로 매핑하고 3-2를 매핑하는 부분 순열을 나타낼 것이다.^[3]두 가지 항목에 대한 7가지 부분 순열은 다음과 같다.

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

콤비네이터 열거

n = 0, 1, 2, ...에 대한 n 항목의 부분 순열 수는 정수 순서에 의해 주어진다.

1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114, 234662231, ...(OEIS의 후속 A002720)

여기서 시퀀스의 n번째 항목은 합계 공식에 의해 주어진다.

${\displaystyle \sum _{i=0}^{n}i!{\binom {n}{i}^{2}}$

i번째 용어에서 크기 i를 지원하는 부분 순열의 수, 즉 i가 홀이 아닌 항목이 있는 부분 순열의 수를 계산한다.또는 반복 관계에 의해 계산될 수 있다.

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

이는 다음과 같이 결정된다.

1. ${\displaystyle P}$( ${\displaystyle n}$- ${\displaystyle 1}$) ${\displaystyle P(n-1)}$ 각 세트의 최종 요소가 생략된 부분$$ 순열:
2. ${\displaystyle P}$( ${\displaystyle n}$- ${\displaystyle 1}$) ${\displaystyle P(n-1)}$ 각 집합의 최종 요소가 서로 매핑되는 부분$$ 순열.
3. ${\displaystyle (}$ ${\displaystyle n}$- ${\displaystyle 1}$) P${\displaystyle }$( ${\displaystyle \mathrm{n}}$- ${\displaystyle 1}$) ${\displaystyle (n-1)P(n-1)}$ 부분$$ 순열은 첫 번째 세트의 최종 요소가 포함되지만 두 번째 세트의 최종 요소에는 매핑되지 않음
4. ${\displaystyle (}$ ${\displaystyle n}$- ${\displaystyle 1}$) P${\displaystyle }$( ${\displaystyle \mathrm{n}}$- ${\displaystyle 1}$) ${\displaystyle (n-1)P(n-1)}$ 부분$$ 순열은 두 번째 세트의 최종 요소가 포함되지만 첫 번째 세트의 최종 요소에는 매핑되지 않음
5. ${\displaystyle -}$( ${\displaystyle n}$- ${\displaystyle 1{}^{}}$) ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}}$( ${\displaystyle \mathrm{n}}$- ${\displaystyle 2}$) ${\displaystyle$ -$(n-1)^{2}P(n-2)},$ 두 세트의 최종 요소가 모두 포함되는 순열, 3과 4에 포함된 부분 순열$,$ 그러나 서로 매핑하지는 마십시오.

부분 순열 제한

일부 저자는 부분 순열을 제한하여 일부^[4] k에 대해 도메인이나 편향 범위^[3] 중 하나가 순열되는 n개 항목 집합의 첫 번째 k 항목으로 구성될 수 밖에 없다.전자의 경우, n-set에서 길이 k의 부분 순열은 반복 없이 n-set에서 k 항의 순서에 불과하다.(초기 콤비네이터학에서는 이러한 물체를 n-set의 "k-permutions"라고 혼동하여 부르기도 한다.)

참조