완전순열 문서 원본 보기

{{위키데이터 속성 추적}}
[[조합론]]에서 '''완전순열'''({{llang|en|complete permutation}}) 또는 '''교란'''({{llang|en|derangement|디레인지먼트}}) 또는 '''교란순열'''은 모든 원소의 위치를 바꾸는 [[순열]]이다.

== 정의 ==
집합 <math>S</math>의 [[순열]] ([[일대일 대응]]) <math>\sigma\colon S\to S</math>가 모든 <math>s\in S</math>에 대하여 다음 성질을 만족시키면, <math>\sigma</math>를 '''완전순열'''이라고 한다.
:<math>\sigma(s)\ne s.</math>
즉, 완전순열은 [[고정점]]이 없는 순열이다.

== 준계승 ==
<math>S</math> [[유한 집합]]이라고 하고, 그 크기를 <math>|S|=n</math>이라고 하자. 그렇다면, <math>n</math>개의 원소에 대한 완전순열의 수를 '''준계승'''({{llang|en|subfactorial|서브팩토리얼}})이라고 한다. 준계승은 기호로 <math>!n</math>으로 쓴다.

준계승에서 <math>P_1 \cup \cdots \cup P_n</math> 의 개수를 빼면 된다.

:<math>!n = (n-1)\left( !(n-1)+!(n-2) \right).</math>
:<math>!n = n \times !(n-1) + (-1)^n.</math>

{| class="wikitable collapsible collapsed"
|-
! 증명
|-
|이 공식들은 [[점화식]]을 사용하여 증명할 수 있다.

집합
:<math>S=\{1,2,3,\dots,n\}</math>
에서 순열 <math>\sigma\colon S\to S</math>가 있을 때, 순열 <math>\sigma</math>의 원소 1은 완전순열이 되기 위하여 1이 아닌 다른 자리에 위치해야 하므로 그 방법의 수는 (n-1)개이다. 이후 경우를 두 가지로 나누어 볼 수 있다.
*'''1이 특정한 자리 x에 위치하고, x가 1의 자리에 위치하는 순열이 될 경우''': 이 경우, 원래의 n개 원소에서 1과 x를 제외한 나머지 (n-2)개의 원소를 사용하는 완전순열이 되므로 !(n-2)로 표현이 가능하다.
*'''1이 특정한 자리 x에 위치하고, x가 1의 자리에 위치하지 않는 순열이 될 경우''': 이 경우, 1은 x의 자리에 위치하였지만, x는 1에 위치하지 않는다는 조건이 있으므로 1과 x를 같은 위상의 원소로 볼 수 있다. 따라서 !(n-1)로 표현이 가능하다.
이상을 종합하여 볼 때, n개의 원소가 갖는 완전순열의 개수 !n은 위 공식으로 주어진다.
|}

:<math>!n = \sum_{k=0}^{n}(-1)^k \binom nk(n-k)! = n! \left( \sum_{k=0}^n{ \frac{(-1)^k}{k!}} \right) = n! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \cdots + (-1)^n \frac{1}{n!} \right).</math>
:<math>!n = \frac{\Gamma (n+1, -1)}{e} = \left[ \frac{n!}{e} \right].</math>

== 외부 링크 ==
* {{eom|title=Inversion (in combinatorics)}}
* {{eom|title=Montmort matching problem}}

{{전거 통제}}

[[분류:순열]]
[[분류:고정점]]
[[분류:정수열]]