완전순열

1. 개요

완전순열은 집합 S의 순열 σ: S → S에서 모든 s ∈ S에 대해 σ(s) ≠ s를 만족하는 순열로, 고정점이 없는 순열을 의미한다. 이러한 완전순열의 개수는 몽모르 수라고도 불리며, 모자 배달 문제와 같이 n개의 항목을 원래 위치에 두지 않도록 하는 경우의 수를 계산하는 문제와 관련이 있다. n개의 원소를 가진 집합의 완전순열의 수 !n은 점화식 !n = (n - 1)(!(n - 1) + !(n - 2)) (n ≥ 2)와 !0 = 1, !1 = 0으로 표현되며, !n = [n!/e]로 근사할 수 있다. 완전순열은 편지를 잘못된 봉투에 넣는 문제나 선물 교환 문제 등 다양한 상황에서 확률 계산에 활용되며, 포함-배제 원리, 생성 함수, 적분 표현 등을 통해 분석된다. 또한, 완전순열은 일반화되어 만남 문제, 아나그램 문제 등으로 확장되며, 주어진 순열군이 교란을 포함하는지 여부를 결정하는 문제는 NP-완전 문제이다.

2. 정의

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

:$\backslash sigma(s)\backslash ne\; s.$

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

어떤 교수가 A, B, C, D 4명의 학생에게 시험을 치르게 하고, 서로의 시험지를 채점하게 하려고 한다고 가정해 보자. 물론, 어떤 학생도 자신의 시험지를 채점해서는 안 된다. 교수가 학생들이 자신의 시험지를 받지 않도록 시험지를 나눠주는 방법은 몇 가지가 있을까? 시험지를 나눠주는 24가지 가능한 순열 (4!) 중, 아래 표와 같다.



완전순열은 9가지(위의 파란색 기울임꼴로 표시)뿐이다. 이 4개의 원소 집합의 다른 모든 순열에서는 적어도 한 명의 학생이 자신의 시험지를 받게 된다(빨간색 굵게 표시).

문제의 또 다른 버전은 서로 다른 사람에게 보내는 n개의 편지를, 올바른 주소가 적힌 봉투에 한 통도 들어가지 않도록 넣는 방법의 수를 묻는 경우에 발생한다.

3. 예시

4명의 학생 A, B, C, D가 시험을 치른 후 서로의 시험지를 바꿔 채점하는 상황을 가정해 보자. 이때, 각 학생이 자신의 시험지를 채점하지 않도록 하는 방법은 다음과 같이 9가지이다.

4. 몽모르 수 (준계승)

$S$를 유한 집합이라 하고, 그 크기를 $|S|=n$이라고 할 때, $n$개의 원소에 대한 완전순열의 수를 준계승(subfactorial^영어)이라고 하며, $!n$으로 쓴다. 이는 프랑스의 수학자 피에르 몽모르의 이름을 따서 명명되었다.

준계승은 다음과 같은 점화식으로 표현할 수 있다.
:$!n\; =\; (n-1)\backslash left(\; !(n-1)+!(n-2)\; \backslash right).$
:$!n\; =\; n\; \backslash times\; !(n-1)\; +\; (-1)^n.$
초기값은 $!0\; =\; 1$, $!1\; =\; 0$이다.

또한, 몽모르 수는 다음과 같은 닫힌 형식으로도 표현할 수 있다.
:$!n\; =\; \backslash sum\_\{k=0\}^\{n\}(-1)^k\; \backslash binom\; nk(n-k)!\; =\; n!\; \backslash left(\; \backslash sum\_\{k=0\}^n\{\; \backslash frac\{(-1)^k\}\{k!\}\}\; \backslash right)\; =\; n!\; \backslash left(\; \backslash frac\{1\}\{0!\}\; -\; \backslash frac\{1\}\{1!\}\; +\; \backslash frac\{1\}\{2!\}\; -\; \backslash cdots\; +\; (-1)^n\; \backslash frac\{1\}\{n!\}\; \backslash right).$
:$!n\; =\; \backslash frac\{\backslash Gamma\; (n+1,\; -1)\}\{e\}\; =\; \backslash left[\; \backslash frac\{n!\}\{e\}\; \backslash right].$

예를 들어, 어떤 교수가 A, B, C, D 4명의 학생에게 시험을 치르게 하고, 서로의 시험지를 채점하게 할 때, 어떤 학생도 자신의 시험지를 채점하지 않도록 하는 방법은 9가지이다.

이 문제는 n개의 편지를 올바른 주소가 적힌 봉투에 한 통도 들어가지 않도록 넣는 방법의 수를 묻는 문제나, n개의 모자를 n명의 사람에게 돌려주되, 어떤 모자도 원래 주인에게 돌아가지 않도록 하는 모자 배달 문제와 같이 생각할 수 있다.

4.1. 몽모르 수 목록

다음은 작은 n에 대한 몽모르 수의 목록이다.

0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, …

5. 점화식

subfactorial^영어이라고도 불리는 완전순열의 수는 다음 점화식으로 나타낼 수 있다.

:$!n\; =\; (n-1)(!(n-1)\; +\; !(n-2))$

:$!n\; =\; n\; \backslash times\; !(n-1)\; +\; (-1)^n$

이 공식은 점화식을 사용하여 증명할 수 있다. 집합 $S=\backslash \{1,\; 2,\; 3,\; \backslash dots,\; n\backslash \}$에서 순열 $\backslash sigma\; \backslash colon\; S\; \backslash to\; S$가 있을 때, 순열 $\backslash sigma$의 원소 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\; =\; \backslash sum\_\{k=0\}^\{n\}(-1)^k\; \backslash binom\; nk(n-k)!\; =\; n!\; \backslash left(\; \backslash sum\_\{k=0\}^n\{\; \backslash frac\{(-1)^k\}\{k!\}\}\; \backslash right)\; =\; n!\; \backslash left(\; \backslash frac\{1\}\{0!\}\; -\; \backslash frac\{1\}\{1!\}\; +\; \backslash frac\{1\}\{2!\}\; -\; \backslash cdots\; +\; (-1)^n\; \backslash frac\{1\}\{n!\}\; \backslash right)$

:$!n\; =\; \backslash frac\{\backslash Gamma\; (n+1,\; -1)\}\{e\}\; =\; \backslash left[\; \backslash frac\{n!\}\{e\}\; \backslash right]$

$!0\; =\; 1$ 및 $!1\; =\; 0$이다.

위에 주어진 공식과 동일한 $!n$에 대한 다른 표현식은 다음과 같다.

:$!n\; =\; n!\; \backslash sum\_\{i=0\}^n\; \backslash frac\{(-1)^i\}\{i!\}$ ($n\; \backslash geq\; 0$)

:$!n\; =\; \backslash left[\; \backslash frac\{n!\}\{e\}\; \backslash right]\; =\; \backslash left\backslash lfloor\backslash frac\{n!\}\{e\}+\backslash frac\{1\}\{2\}\backslash right\backslash rfloor$ ($n\; \backslash geq\; 1$)

여기서 $\backslash left[\; x\backslash right]$는 가장 가까운 정수 함수이고 $\backslash left\backslash lfloor\; x\; \backslash right\backslash rfloor$는 바닥 함수이다.

기타 관련 공식은 다음과 같다.

:$!n\; =\; \backslash left\backslash lfloor\; \backslash frac\{n!+1\}\{e\}\; \backslash right\backslash rfloor$ ($n\; \backslash ge\; 1$)

:$!n\; =\; \backslash left\backslash lfloor\; \backslash left(e\; +\; e^\{-1\}\backslash right)n!\backslash right\backslash rfloor\; -\; \backslash lfloor\; en!\backslash rfloor$ ($n\; \backslash geq\; 2$)

:$!n\; =\; n!\; -\; \backslash sum\_\{i=1\}^n\; \{n\; \backslash choose\; i\}\; \backslash cdot\; \{!(n\; -\; i)\}$ ($n\; \backslash ge\; 1$)

다음 재귀 관계식도 성립한다.

:$$
!n = \begin{cases}
1 & \text{if } n = 0, \\
n \cdot \left( !(n-1) \right) + (-1)^n & \text{if }n > 0.
\end{cases}

몽모르 수 $a\_n$를 나타내는 점화식은 다음과 같다.

:$a\_n=(n-1)(a\_\{n-1\}+a\_\{n-2\})$ ($n\; \backslash geqq\; 3$)

$a\_2\; =\; 1$을 점화식에 대입하면 $a\_0\; =\; 1$이 얻어지므로, 일반항은 다음과 같다.

:$a\_n=\backslash sum\_\{k=0\}^n\{\backslash frac\{(-1)^k\; n!\}\{k!\}\}$ ($n\; \backslash geqq\; 0$)

일반항으로부터, 다른 점화식 $a\_n=n\; a\_\{n-1\}+(-1)^\{n\}$ ($n\; \backslash geqq\; 1$)을 얻을 수 있다.

6. 확률

$n$개의 원소를 무작위로 섞을 때, 완전순열이 될 확률은 $\backslash frac\{!n\}\{n!\}$이다. 이 확률은 $n$이 커짐에 따라 $\backslash frac\{1\}\{e\}$ (약 0.367879)로 수렴한다.

완전 순열 확률과 관련된 공식은 다음과 같다.

:$!n\; =\; n!\; \backslash sum\_\{i=0\}^n\; \backslash frac\{(-1)^i\}\{i!\}$ ($n\; \backslash geq\; 0$)

:$\backslash lim\_\{n\backslash to\backslash infty\}\; \backslash frac\{!n\}\{n!\}\; =\; \backslash lim\_\{n\backslash to\backslash infty\}\; \backslash sum\_\{i=0\}^n\; \backslash frac\{(-1)^i\}\{i!\}\; =\; e^\{-1\}\; \backslash approx\; 0.367879\backslash ldots.$

예를 들어, 5명이 선물을 가져와 무작위로 다시 나누어 가질 때, 누군가가 자신이 가져온 선물에 당첨될 확률 $p\_5$는 다음과 같다.

:$p\_5=\backslash dfrac\{5\; !-44\}\{5\; !\}=\backslash dfrac\{76\}\{120\}=\backslash dfrac\{19\}\{30\}=0.6333\backslash cdots$

10명이 선물을 가져와 무작위로 다시 나누어 가질 때의 확률 $p\_\{10\}$는 다음과 같다.

:$p\_\{10\}=\backslash dfrac\{10\; !-1334961\}\{10\; !\}=\backslash dfrac\{2293839\}\{3628800\}=0.63212053571428571428571428571429\backslash cdots$

따라서, $n$명이 선물을 가져와 무작위로 다시 나누어 가질 때, 누군가가 자신이 가져온 선물에 당첨될 확률 $p\_n$의 극한은 다음과 같다.

:$\backslash lim\_\{n\; \backslash to\; \backslash infty\}p\_n\; =\; 1\; -\; \backslash frac\{1\}\{e\}\; =\; 0.63212055882855767840447622983854\backslash cdots$

7. 포함-배제 원리

subfactorial^영어이라고 불리는 몽모르 수의 일반항은 포함-배제 원리를 사용하여 유도할 수 있다. 1 ≦ k ≦ n을 만족하는 자연수 k에 대해, 집합 $A\_k$를 n개의 숫자 를 자신에게 매핑하는 순열 중에서, k번째 숫자를 고정하는 (즉, k를 k에 매핑하는) 순열의 집합이라고 하자. i개의 집합의 교집합은 i개의 숫자를 고정하는 순열을 시행한 순열이 되므로, 그 원소의 개수는 $(n\; -\; i)!$와 같다. 이때, 교집합을 선택하는 방법은 $\_\{n\}\backslash mathrm\{C\}\_\{i\}\; =\; \backslash tbinom\{n\}\{i\}$ 가지가 되므로, 포함-배제 원리에 의해 다음 식이 성립한다.

:
- \sum_{i < j} \left|A_i\cap A_j\right|
+ \sum_{i < j < k} \left|A_i\cap A_j\cap A_k\right|
+ \cdots
+ (-1)^{n + 1} \left|A_1\cap \cdots \cap A_n\right|\\
&={n\choose 1}(n-1)!-{n\choose 2}(n-2)!+{n\choose 3}(n-3)!-\cdots+(-1)^{n+1}{n\choose n} 0!\\
&=\sum_{i=1}^n (-1)^{i+1}{n\choose i}(n-i)!\\
&=n!\ \sum_{i=1}^n {(-1)^{i+1}\over i!}
\end{align}

이때, 완전 순열은 n개의 숫자 중 어느 것도 고정하지 않는 순열에 의한 순열이 되므로, 다음 식을 얻는다.

:$a\_n\; =\; n!-\; |A\_1\backslash cup\backslash cdots\backslash cup\; A\_n|=n!\; \backslash sum\_\{i=0\}^n\; \backslash frac\{(-1)^i\}\{i!\}.$

8. 생성 함수

몽모르 수 $a\_n$에 대한 생성 함수는 다음과 같다.

:
&= 1+x^2+2x^3+9x^4+44x^5+265x^6+\cdots\end{align}

여기서 $\backslash mathrm\{Ei\}$는 지수 적분이다. 또한, 지수형 생성 함수는 다음과 같다.

:
&= 1+\frac{1}{2}x^2+\frac{1}{3}x^3+\frac{3}{8}x^4+\frac{11}{30}x^5+\frac{53}{144}x^6+\cdots\end{align}

여기서 계수의 분자 열은 OEIS의 A053557을, 분모 열은 A053556을 참조한다.

9. 계산식

몽모르 수는 다음과 같은 식으로도 계산할 수 있다.

:$!n\; =\; (n-1)\backslash left(\; !(n-1)+!(n-2)\; \backslash right).$
:$!n\; =\; n\; \backslash times\; !(n-1)\; +\; (-1)^n.$
:$!n\; =\; \backslash sum\_\{k=0\}^\{n\}(-1)^k\; \backslash binom\; nk(n-k)!\; =\; n!\; \backslash left(\; \backslash sum\_\{k=0\}^n\{\; \backslash frac\{(-1)^k\}\{k!\}\}\; \backslash right)\; =\; n!\; \backslash left(\; \backslash frac\{1\}\{0!\}\; -\; \backslash frac\{1\}\{1!\}\; +\; \backslash frac\{1\}\{2!\}\; -\; \backslash cdots\; +\; (-1)^n\; \backslash frac\{1\}\{n!\}\; \backslash right).$
:$!n\; =\; \backslash frac\{\backslash Gamma\; (n+1,\; -1)\}\{e\}\; =\; \backslash left[\; \backslash frac\{n!\}\{e\}\; \backslash right].$

이 공식들은 점화식을 사용하여 증명할 수 있다.

작은 길이의 완전 순열 수는 아래 표에 나와 있다.

위에 주어진 공식과 동일한 !n에 대한 다른 표현식은 다음과 같다.
:$!n\; =\; n!\; \backslash sum\_\{i=0\}^n\; \backslash frac\{(-1)^i\}\{i!\}$ ($n\; \backslash geq\; 0$)
:$!n\; =\; \backslash left[\; \backslash frac\{n!\}\{e\}\; \backslash right]\; =\; \backslash left\backslash lfloor\backslash frac\{n!\}\{e\}+\backslash frac\{1\}\{2\}\backslash right\backslash rfloor$ ($n\; \backslash geq\; 1$)

여기서 $\backslash left[\; x\backslash right]$는 가장 가까운 정수 함수이고 $\backslash left\backslash lfloor\; x\; \backslash right\backslash rfloor$는 바닥 함수이다.

기타 관련 공식은 다음과 같다.
:$!n\; =\; \backslash left\backslash lfloor\; \backslash frac\{n!+1\}\{e\}\; \backslash right\backslash rfloor$ ($n\; \backslash ge\; 1$)
:$!n\; =\; \backslash left\backslash lfloor\; \backslash left(e\; +\; e^\{-1\}\backslash right)n!\backslash right\backslash rfloor\; -\; \backslash lfloor\; en!\backslash rfloor$ ($n\; \backslash geq\; 2$)
:$!n\; =\; n!\; -\; \backslash sum\_\{i=1\}^n\; \{n\; \backslash choose\; i\}\; \backslash cdot\; \{!(n\; -\; i)\}$ ($n\; \backslash ge\; 1$)

다음 재귀 관계식도 성립한다.
:$!n\; =\; \backslash begin\{cases\}$
1 & \text{if } n = 0, \\
n \cdot \left( !(n-1) \right) + (-1)^n & \text{if }n > 0.
\end{cases}

$x\; =\; -1$을 대입하면 다음을 얻을 수 있다.
:$\backslash lim\_\{n\backslash to\backslash infty\}\; \{!n\; \backslash over\; n!\}\; =\; \backslash lim\_\{n\backslash to\backslash infty\}\; \backslash sum\_\{i=0\}^n\; \backslash frac\{(-1)^i\}\{i!\}\; =\; e^\{-1\}\; \backslash approx\; 0.367879\backslash ldots.$

다른 계산식으로는 다음과 같은 식이 있다.
:$a\_\{n\}\; =\; \backslash left\backslash lfloor\; \backslash frac\{n!\}\{e\}\; \backslash right\backslash rceil$ ($n\; \backslash geqq\; 1$)
여기서, $\backslash left\backslash lfloor\; x\; \backslash right\backslash rceil$는 x의 소수점 이하를 반올림한 값이다.

또한,
:$a\_\{n\}\; =\; \backslash left\backslash lfloor\; \backslash frac\{n!+1\}\{e\}\; \backslash right\backslash rfloor$ ($n\; \backslash geqq\; 1$)
여기서, $\backslash left\backslash lfloor\; x\; \backslash right\backslash rfloor$는 바닥 함수의 값이다.

10. 적분 표현

불완전 감마 함수 Γ(a, x)^영어를 사용하여 몽모르 수(준계승)를 다음과 같이 나타낼 수 있다.

:$!n\; =\; \backslash frac\{\backslash Gamma(n\; +\; 1,\; -1)\}\{e\}.$

이는 불완전 감마 함수의 적분 표현을 통해 다음과 같이 나타낼 수 있다.

:$!n\; =\; \backslash int\_\{-1\}^\{\backslash infty\}x^\{n\}e^\{-(x+1)\}dx\; =\backslash int\_0^\backslash infty(x-1)^ne^\{-x\}dx.$

11. 점근 전개

벨 수를 사용하여 몽모르 수의 점근 전개를 나타낼 수 있다.

:$!n\; =\; \backslash frac\{n!\}\{e\}\; +\; \backslash sum\_\{k=1\}^m\; \backslash left(-1\backslash right)^\{n+k-1\}\backslash frac\{B\_k\}\{n^k\}\; +\; O\backslash left(\backslash frac\{1\}\{n^\{m+1\}\}\backslash right)$

여기서 $m$은 임의의 고정된 양의 정수이고, $B\_k$는 $k$번째 벨 수를 나타낸다. 또한, 빅 오 항에 의해 암시되는 상수는 $B\_\{m+1\}$을 초과하지 않는다.

12. 일반화

만남 문제는 크기-n 집합의 순열 중 정확히 k개의 고정점을 갖는 순열이 몇 개인지 묻는 문제이다.

교란 순열은 제약된 순열의 더 넓은 분야의 한 예이다. 예를 들어, 메나주 문제는 n쌍의 이성 커플이 원탁에 남-여-남-여-... 순으로 앉아 있을 때, 아무도 파트너 옆에 앉지 않도록 앉는 방법이 몇 가지인지 묻는다.

더 형식적으로, 집합 A와 S, 그리고 전사 함수 A → S의 집합 U와 V가 주어질 때, U에 속하는 f와 V에 속하는 g의 쌍의 개수를 알고 싶어하며, 모든 a in A에 대해 f(a) ≠ g(a)이다. 즉, 각 f와 g에 대해, S의 교란 순열 φ가 존재하여 f(a) = φ(g(a))인 경우이다.

또 다른 일반화는 다음과 같다.

:주어진 단어에서 고정된 글자가 없는 아나그램은 몇 개나 있을까요?

예를 들어, 두 개의 서로 다른 문자만으로 구성된 단어, 즉 n개의 문자 A와 m개의 문자 B의 경우, 고정된 문자가 없는 아나그램을 형성하는 유일한 방법은 모든 A를 B로 바꾸는 것이고, 이것은 n = m인 경우에만 가능하므로 답은 1 또는 0이다. 일반적인 경우, n₁개의 문자 X₁, n₂개의 문자 X₂, ..., n_r개의 문자 X_r로 구성된 단어의 경우, (포함-배제 원리 공식을 적절히 사용하면) 답이 다음과 같은 형태를 갖는 것으로 나타난다.
$$\backslash int\_0^\backslash infty\; P\_\{n\_1\}(x)\; P\_\{n\_2\}(x)\; \backslash cdots\; P\_\{n\_r\}(x)\backslash \; e^\{-x\}\; dx,$$
어떤 일련의 다항식 P_n에 대해, 여기서 P_n의 차수는 n이다. 그러나 r = 2인 경우 위의 답은 직교 관계를 제공하므로 P_n는 라게르 다항식이다 (부호는 쉽게 결정된다).

특히, 고전적인 교란 순열의 경우 다음과 같다.
$$!n\; =\; \backslash frac\{\; \backslash Gamma(n+1,-1)\; \}\{\; e\; \}\; =\; \backslash int\_0^\backslash infty(x\; -\; 1)^n\; e^\{-x\}\; dx$$
여기서 $\backslash Gamma(s,x)$는 불완전 감마 함수이다.

13. 계산 복잡도

주어진 순열군(이를 생성하는 순열 집합으로 설명됨)이 교란을 포함하는지 여부를 결정하는 문제는 NP-완전이다.