교란순열 (Derangement)
한 줄 정의: 어떤 원소도 원래 자리에 남지 않도록 배열하는 순열입니다.
쉽게 풀면
n개의 편지를 n개의 봉투에 넣는데 모든 편지가 엉뚱한 봉투에 들어가는 경우를 세는 문제입니다. 이렇게 어느 것도 제자리에 있지 않은 순열을 교란순열이라 합니다. n이 커지면 전체 순열 중 교란순열의 비율은 자연상수 e의 역수, 약 0.368에 수렴합니다.
왜 중요한가
포함배제원리의 가장 대표적인 응용 예제로 조합론 교재에 반드시 등장하며, 임의 배정에서 우연한 일치가 하나도 없을 확률을 계산하는 표준 모형입니다. 실험 설계에서 처리를 무작위로 재배정하거나 무작위 검정의 기준 분포를 세울 때도 활용됩니다.
논문에서는 이렇게 쓰입니다
"무작위 재배정에서 원래 짝이 하나도 유지되지 않을 확률을 교란순열의 개수로 계산하였다."
조금 더 깊게 보면
교란순열의 개수는 포함배제원리로 n 팩토리얼에 부호가 번갈아 바뀌는 역팩토리얼 급수를 곱한 형태로 얻어집니다. 이 급수가 e의 역수의 테일러 전개와 같아 비율이 그 값으로 수렴합니다. 점화식으로는 앞의 두 항을 이용하는 관계식이 성립하며, 가장 가까운 정수로 반올림하는 간단한 근사 공식도 널리 쓰입니다. 정확히 k개만 제자리에 있는 순열의 개수도 이 값으로 표현됩니다.
주의할 점
교란순열의 비율이 e의 역수에 가깝다는 사실은 n이 커질 때의 극한이며, 실제로는 n이 5 정도만 되어도 근사가 매우 좋습니다. 원소가 서로 구별되지 않는 상황에는 이 공식을 쓸 수 없습니다.