완전순열
(완전 순열에서 넘어옴)
조합론에서 완전순열(영어: complete permutation) 또는 교란(영어: derangement 디레인지먼트[*])은 모든 원소의 위치를 바꾸는 순열이다.
정의 편집
집합 의 순열 (일대일 대응) 가 모든 에 대하여 다음 성질을 만족시키면, 를 완전순열이라고 한다.
즉, 완전순열은 고정점이 없는 순열이다.
준계승 편집
유한 집합이라고 하고, 그 크기를 이라고 하자. 그렇다면, 개의 원소에 대한 완전순열의 수를 준계승(영어: subfactorial 서브팩토리얼[*])이라고 한다. 준계승은 기호로 으로 쓴다.
준계승에서 의 개수를 빼면 된다.
증명 |
---|
이 공식들은 점화식을 사용하여 증명할 수 있다.
집합 에서 순열 가 있을 때, 순열 의 원소 1은 완전순열이 되기 위하여 1이 아닌 다른 자리에 위치해야 하므로 그 방법의 수는 (n-1)개이다. 이후 경우를 두 가지로 나누어 볼 수 있다.
이상을 종합하여 볼 때, n개의 원소가 갖는 완전순열의 개수 !n은 위 공식으로 주어진다. |
외부 링크 편집
- “Inversion (in combinatorics)”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- “Montmort matching problem”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.