조합론에서 완전순열(영어: complete permutation) 또는 교란(영어: derangement 디레인지먼트[*])은 모든 원소의 위치를 바꾸는 순열이다.
집합
의 순열 (일대일 대응)
가 모든
에 대하여 다음 성질을 만족시키면,
를 완전순열이라고 한다.
![{\displaystyle \sigma (s)\neq s.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d9e3bed8234af145651dbbf69fa360300e46a971)
즉, 완전순열은 고정점이 없는 순열이다.
준계승[편집]
유한 집합이라고 하고, 그 크기를
이라고 하자. 그렇다면,
개의 원소에 대한 완전순열의 수를 준계승(영어: subfactorial 서브팩토리얼[*])이라고 한다. 준계승은 기호로
으로 쓴다.
준계승에서
의 개수를 빼면 된다.
![{\displaystyle !n=(n-1)\left(!(n-1)+!(n-2)\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e440f5707676088df5be172d5150c43f5e431067)
![{\displaystyle !n=n\times !(n-1)+(-1)^{n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6faaac540ea0de0daa2cde6639c2dc6f232c2e41)
증명
|
이 공식들은 점화식을 사용하여 증명할 수 있다.
집합
![{\displaystyle S=\{1,2,3,\dots ,n\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cae4d442a2bce94e26eb91d1ab08b5e7d97dfef4)
에서 순열 가 있을 때, 순열 의 원소 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은 위 공식으로 주어진다.
|
![{\displaystyle !n=\sum _{k=0}^{n}(-1)^{k}{\binom {n}{k}}(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).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5cd0f8c75545896a61b0623fa0e357b842a06653)
![{\displaystyle !n={\frac {\Gamma (n+1,-1)}{e}}=\left[{\frac {n!}{e}}\right].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e754bc8139b20ef2aee65e7063155ff75803f5e7)
외부 링크[편집]