이 글에서는 포함-배제 원리의 응용으로서 교란 순열의 성질과 오일러 함수의 일반항을 살펴봅니다. 이 글은 Jiří Matoušek 교수님과 Jaroslav Nešetřil 교수님의 책 『Invitation to Discrete Mathematics』 2판 3.8절의 내용을 참고하여 작성하였습니다.
교란순열
다음과 같은 문제를 생각해 보자.
문제. 세 명의 사람이 같은 모양의 모자를 쓰고 있다. 이름이 모자의 안쪽에 적혀 있어서, 모자를 들어서 이름표를 확인하기 전에는 모자를 구분할 수 없다. 세 명이 모자를 모두 벗어놓고 일을 보러 갔다가 다시 모자를 쓰러 왔는데, 어느 모자를 어디에 두었는지 기억하지 못하여 임의로 하나씩 집어들었다. 이때 세 명 모두 다른 사람의 모자를 집어들 가능성은 얼마일까?
세 명이 임의로 하나씩 모자를 택하는 경우의 수는 \(3! = 6\)이며, 이 여섯 가지 중 어느 누구도 자신의 모자를 택하지 않는 경우의 수는(모든 경우를 헤아려 보면) \(2\)이므로, 문제의 답은 \[\frac{2}{6} = \frac{1}{3}\] 이다. 만약 사람 수가 \(n\)이라면 어떠할까?
정의역과 공역이 모두 집합 \(I_n = \left\{1,\,2,\,3,\,\cdots,\,n\right\}\)인 일대일대응을 순열 또는 치환이라고 부른다. 순열 중에서 고정점을 갖지 않는 것의 수를 교란순열(derangement) 또는 완전순열이라고 부른다. \(I_n\) 위에서의 교란순열의 개수를 \(D(n)\)으로 나타내자. [주의: \(D_n\)은 교란순열이 아니다. \(D(n)\)은 교란순열의 개수이다. 책에 따라서는 \(D(n)\)을 \(!n\)으로 나타내기도 한다.]
위 문제는 \(n=3\)일 때 \(D(3) / 3!\)의 값을 구하는 문제이다. 일반적으로 자연수 \(n\)에 대하여 \(D(n) / n!\)의 값을 구하는 문제를 ‘Hat-check problem’이라고 부른다.
교란순열의 일반항을 구하는 방법은 여러 가지가 있다. 여기서는 포함-배제 원리를 이용한 방법을 살펴 보자.
\(I_n\) 위에서의 치환들의 모임을 \(S_n\)으로 나타내고 \[A_i = \left\{ \pi \in S_n \,\vert\,\pi (i) = i \right\}\] 라고 하자. 즉 \(I_n\) 위에서의 치환 중에서 \(i\)를 부동점(fixed point)으로 갖는 것들의 모임이 \(A_i\)이다. 이러한 \(A_i\)들을 모두 합집합하면, 그 집합이 바로 정확히 교란순열이 아닌 순열들의 모임이 된다. 그러므로 \[D(n) = n! - \left\lvert \bigcup_{i=1}^n A_i \right\rvert\tag{1}\] 를 구하면 \(D(n)\)의 일반항이 된다.
명백히 \(\lvert A_i \rvert = (n-1)!\)이다. 왜냐하면 \(A_i\)는 \(I_n\)의 원소 중 \(i\)만 고정시키고 다른 원소들을 일대일로 대응시키는 순열들의 개수이기 때문이다. 마찬가지로 \(i\ne j\)일 때 \[\lvert A_i \cap A_j \rvert = (n-2)!\] 이다. 왜냐하면 \(A_i \cap A_j\)는 \(I_n\)의 원소 중 \(i,\) \(j\)만 고정시키고 다른 원소들을 일대일로 대응시키는 순열들의 개수이기 때문이다. 더 일반적으로 \(n\) 이하인 서로 다른 \(k\)개의 자연수 \(i_1,\) \(i_2,\) \(\cdots,\) \(i_k\)가 있을 때 \[\left\lvert A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k} \right\rvert = (n-k)!\] 이다. 그러므로 포함-배제 원리에 의하여 다음을 얻는다. \[\begin{align} \left\lvert A_1 \cup A_2 \cup \cdots \cup A_n \right\rvert &= \sum_{k=1}^{n} (-1)^{k-1} \binom{n}{k} (n-k)! \\[5pt] &= \sum_{k=1}^{n} (-1)^{k-1} \frac{n!}{k!}.\tag{2} \end{align}\] (1)과 (2)를 결합하면 다음을 얻는다. \[D(n) = n! \left( 1- \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + - \cdots + (-1)^n \frac{1}{n!} \right).\tag{3}\] 이로써 \(n\)명에 대한 Hat-check problem의 답은 다음과 같다. \[\frac{D(n)}{n!} = 1- \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + - \cdots + (-1)^n \frac{1}{n!} \tag{4}\] 여기에 \(n\,\rightarrow\,\infty\)인 극한을 취하면 다음을 얻는다. \[\lim_{n\rightarrow\infty} \frac{D(n)}{n!} = 1- \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + - \cdots = \frac{1}{e}.\tag{5}\] 즉 많은 사람들이 자기 물건을 하나씩 꺼내어 섞은 뒤 임의로 하나씩 집었을 때, 모든 사람이 자신의 것이 아닌 물건을 집을 확률은 \(1/e\)에 가깝다. 여기서 \(e\)는 자연상수 \[e = 2.718281828459045\cdots\] 이다.
오일러 파이 함수
\(n\)이 자연수일 때, \(n\) 이하의 자연수 중 \(n\)과 서로소인 것들의 수를 \(\varphi(n)\)으로 나타낸다. 이러한 함수 \(\varphi(n)\)을 오일러 함수(Euler function) 또는 ‘오일러 파이 함수’라고 부른다. 오일러 함수는 다음과 같이 나타낼 수 있다. \[\varphi (n) = \left\lvert \left\{ m \in I_n \,\vert\, \gcd (n,\,m) = 1\right\} \right\rvert .\tag{6}\] 오일러 함수의 일반항을 구해 보자. 가장 간단한 경우는 \(n\)이 소수인 경우, \(n=p\)인 경우이다. 이때는 \[\varphi(p) = p-1\] 이다. 다음으로 \(n\)이 소수의 거듭제곱인 경우, 즉 \(n=p^{\alpha},\) \(\alpha\in\mathbb{N}\)인 경우이다. 이때 \(p^{\alpha}\) 이하의 자연수 중 이 수와 서로소가 아닌 것들은 다음과 같다. \[p,\,\, 2p ,\,\, 3p ,\,\, \cdots ,\,\, p^{\alpha -1}p\] 이 수들의 개수는 \(p^{\alpha -1}\)이다. 그러므로 \(p^{\alpha}\)의 오일러 함숫값은 다음과 같다. \[\varphi(p^{\alpha}) = p^{\alpha} - p^{\alpha -1} = p^{\alpha} \left( 1-\frac{1}{p}\right).\tag{7}\] 이제 \(n\)이 임의의 자연수이고 다음과 같이 소인수분해된다고 하자. \[n=p_1 ^{\alpha_1} p_2 ^{\alpha_2} \cdots p_r ^{\alpha_r}.\tag{8}\] 여기서 \(p_1 ,\) \(p_2,\) \(\cdots,\) \(p_r\)들은 모두 서로 다른 소수이고 \(\alpha_i\)는 자연수이다. \(n\) 이하의 자연수 중 \(n\)과 서로소가 아닌 것은 (8)의 밑에 나타나는 소수 \(p_i\) 중 하나 이상을 인수(약수)로 갖는 것이다. \(n\) 이하의 자연수 중 \(p_i\)의 배수의 집합을 다음과 같이 나타내자. \[A_i = \left\{ m\in I_n \,\vert\, p_i \text{ divides } m \right\}.\] 그러면 다음을 얻는다. \[\varphi(n) = n- \left\lvert A_1 \cup A_2 \cup A_3 \cup \cdots \cup A_r \right\rvert. \tag{9}\] (8)의 밑에 나타나는 소수 중 서로 다른 두 개 \(p_i ,\) \(p_j\)가 있을 때, \(A_i \cap A_j\)는 \(p_i\)와 \(p_j\)의 공배수들의 모임, 즉 \(p_i p_j\)의 배수의 모임이다. 그러므로 \[\lvert A_i \cap A_j \rvert = \frac{n}{p_1 p_2 }\] 이다. 마찬가지로 \[\left\lvert A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}\right\rvert = \frac{n}{p_{i_1} p_{i_2} \cdots p_{i_k}}\tag{10}\] 이다. (9)와 (10)을 결합하고 포함-배제 원리를 이용하면 \(\varphi(n)\)의 일반항을 구할 수 있다. 그 전에 (8)에서 \(r=2\) 또는 \(r=3\)인 경우를 먼저 생각해 보자. \(n=p_1 ^{\alpha_1} p_2 ^{\alpha_2}\)이면 다음을 얻는다. \[\begin{align} \varphi(n) &= n - \lvert A_1 \cup A_2 \rvert \\[5pt] &= n - \lvert A_1 \rvert - \lvert A_2 \rvert + \lvert A_1 \cap A_2 \rvert \\[5pt] &= n - \frac{n}{p_1} - \frac{n}{p_2} + \frac{n}{p_1 p_2} \\[5pt] &= n \left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right). \end{align}\] 비슷하게, \(n = p_1^{\alpha_1} p_2 ^{\alpha_2} p_3 ^{\alpha_3}\)이면 다음을 얻는다. \[\begin{align} \varphi(n) &= n - \frac{n}{p_1} - \frac{n}{p_2} - \frac{n}{p_3} + \frac{n}{p_1 p_2} + \frac{n}{p_2 p_3} + \frac{n}{p_3 p_1} - \frac{n}{p_1 p_2 p_3 }\\[5pt] &= n\left( 1- \frac{1}{p_1} \right) \left( 1-\frac{1}{p_2} \right) \left( 1- \frac{1}{p_3}\right). \end{align}\] 관찰한 내용을 일반화하면 다음 결과를 얻는다.
정리. \(n\)이 자연수이고 그 소인수분해가 \(n=p_1 ^{\alpha_1} p_2 ^{\alpha_2} \cdots p_r^{\alpha_r}\)일 때 다음이 성립한다. \[\varphi(n) = n \left( 1- \frac{1}{p_1} \right) \left( 1- \frac{1}{p_2} \right) \cdots \left( 1-\frac{1}{p_r} \right).\tag{11}\]
증명.
포함-배제 원리에 의하여 다음이 성립한다. (참고: 포함-배제 원리의 세 가지 증명) \[\varphi(n) = n-\sum_{\varnothing \ne I \subseteq I_r} (-1)^{\lvert I \rvert -1} \frac{n}{\prod_{i\in I} p_i} = n \sum_{I\subseteq I_r} \frac{(-1)^{\lvert I \rvert}}{\prod_{i\in I} p_i}.\tag{12}\] 그런데 이 식의 우변은 등식 \[(1+x_1)(1+x_2)\cdots(1+x_n) = \sum_{I\subseteq I_n} \left( \prod_{i\in I} x_i \right)\tag{13}\] 의 우변에 \(x_i = -1/p_i ,\) \(i=1,\,2,\,\cdots,\,r\)를 대입하고 \(n\)을 곱한 것과 같다.
(13)의 좌변에 \(n\)을 곱하면 (11)의 우변과 같다.