완전순열

틀:위키데이터 속성 추적 조합론에서 완전순열(틀:Llang) 또는 교란(틀:Llang) 또는 교란순열은 모든 원소의 위치를 바꾸는 순열이다.

정의

집합 $S$ 의 순열 (일대일 대응) $σ : S \to S$ 가 모든 $s \in S$ 에 대하여 다음 성질을 만족시키면, $σ$ 를 완전순열이라고 한다.

σ (s) \neq s .

즉, 완전순열은 고정점이 없는 순열이다.

$S$ 유한 집합이라고 하고, 그 크기를 $| S | = n$ 이라고 하자. 그렇다면, $n$ 개의 원소에 대한 완전순열의 수를 준계승(틀:Llang)이라고 한다. 준계승은 기호로 $! n$ 으로 쓴다.

준계승에서 $P_{1} \cup \dots \cup P_{n}$ 의 개수를 빼면 된다.

! n = (n - 1) (! (n - 1) +! (n - 2)) .

! n = n \times! (n - 1) + (- 1)^{n} .

증명
이 공식들은 점화식을 사용하여 증명할 수 있다. 집합 $S = {1, 2, 3, \dots, n}$ 에서 순열 $σ : S \to S$ 가 있을 때, 순열 $σ$ 의 원소 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은 위 공식으로 주어진다.

! n = \sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) (n - k)! = n! (\sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!}) = n! (\frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \dots + (- 1)^{n} \frac{1}{n!}) .

! n = \frac{Γ (n + 1, - 1)}{e} = [\frac{n!}{e}] .