완전순열

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]

4. 1. 몽모르 수 목록

5. 점화식

subfactorial|서브팩토리얼^영어이라고도 불리는 완전순열의 수는 다음 점화식으로 나타낼 수 있다.^[14]

:$!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)$로 표현이 가능하다.

6. 확률

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

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

:$!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|서브팩토리얼^영어이라고 불리는 몽모르 수의 일반항은 포함-배제 원리를 사용하여 유도할 수 있다.^[8] 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|

8. 생성 함수

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

:

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

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

:

&= 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].$

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

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

위에 주어진 공식과 동일한 !''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$는 바닥 함수이다.^[6][5]

기타 관련 공식은 다음과 같다.^[6][7]

:$!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$)

다음 재귀 관계식도 성립한다.^[5]

:$!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.$

다른 계산식으로는 다음과 같은 식이 있다.^[14]

:$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$는 바닥 함수의 값이다.^[13]

10. 적분 표현

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

:$!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. 점근 전개

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

:$!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\}$을 초과하지 않는다.^[9]

12. 일반화

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

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

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

또 다른 일반화는 다음과 같다.^[10]

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

예를 들어, 두 개의 서로 다른 문자만으로 구성된 단어, 즉 ''n''개의 문자 A와 ''m''개의 문자 B의 경우, 고정된 문자가 없는 아나그램을 형성하는 유일한 방법은 모든 ''A''를 ''B''로 바꾸는 것이고, 이것은 ''n'' = ''m''인 경우에만 가능하므로 답은 1 또는 0이다. 일반적인 경우, ''n''₁개의 문자 ''X''₁, ''n''₂개의 문자 ''X''₂, ..., ''n''_''r''개의 문자 ''X''_''r''로 구성된 단어의 경우, (포함-배제 원리 공식을 적절히 사용하면) 답이 다음과 같은 형태를 갖는 것으로 나타난다.^[10]

$$\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''는 라게르 다항식이다 (부호는 쉽게 결정된다).^[10]

13. 계산 복잡도

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

참조

_[1] 서적 A History of Mathematical Notations: Two volumes in one https://books.google[...] Cosimo, Inc.
_[2] 서적 Concrete Mathematics Addison–Wesley
_[3] 서적 Essay d'analyse sur les jeux de hazard Jacque Quillau (1708) / Jacque Quillau (1713)
_[4] 간행물 The Hat-Check Problem
_[5] 서적 Enumerative Combinatorics, volume 1 Cambridge University Press
_[6] 간행물 Derangements and applications http://www.cs.uwater[...]
_[7] MathWorld Subfactorial
_[8] 간행물 A note on derangements 1967-05
_[9] 간행물 Derangements and Alternating Sum of Permutations by Integration
_[10] 간행물 Derangements and Laguerre polynomials http://journals.camb[...] 2011-12-27
_[11] 간행물 Some NP-complete problems similar to graph isomorphism
_[12] 서적 Handbook of Combinatorics http://people.cs.uch[...] Elsevier
_[13] MathWorld Subfactorial
_[14] MathWorld Derangement