정리 1.7.1. 포함배제의 원리_{(inclusion-exclusion principle)}

$I = \{1,\, 2,\, \ldots,\, n\}$이라 하자. 유한개의 집합 $A_1,\, A_2,\, \ldots,\, A_n$에 대하여, \begin{align*} & \abs{A_1 \cup A_2 \cup \cdots \cup A_n} = \sum_{k=1}^{n} \sum_{\substack{J \subset I \\ \abs{J} = k}} (-1)^{k+1} \bigg| \bigcap_{j \in J} A_j \bigg|. \end{align*}

$ $

예제 1.7.2.
Q. 양의 정수 $n$이 \[ n = p^a q^b r^c \] 와 같이 소인수분해된다고 할 때, $1$부터 $n$까지의 양의 정수 중 $n$과 서로소인 양의 정수의 개수를 구하여라.
A. 전체집합을 $X = \{1,\ 2,\, \ldots,\, n\}$이라 하고, 세 집합 $A_p$, $A_q$, $A_r$를 각각 $1$부터 $n$까지의 양의 정수 중 $p,\, q,\, r$의 배수의 집합으로 정의하자. 그러면 \begin{align*} & \abs{A_p} = \frac{n}{p}, \quad \abs{A_q} = \frac{n}{q}, \quad \abs{A_r} = \frac{n}{r}, \\[1ex] & \abs{A_p \cap A_q} = \frac{n}{pq}, \quad \abs{A_p \cap A_r} = \frac{n}{pr}, \quad \abs{A_q \cap A_r} = \frac{n}{qr}, \\[1ex] & \abs{A_p \cap A_q \cap A_r} = \frac{n}{pqr}. \end{align*} 따라서 포함배제의 원리에 의해 \begin{align*} \abs{A_p^c \cap A_q^c \cap A_r^c} & = \abs{X} - \abs{A_p \cup A_q \cup A_r} \\[1ex] & = n - \left[ \bigg( \frac{n}{p} + \frac{n}{q} + \frac{n}{r} \bigg) - \bigg( \frac{n}{pq} + \frac{n}{pr} + \frac{n}{qr} \bigg) + \frac{n}{pqr} \right] \\[1ex] & = n \left[ 1 - \bigg( \frac{1}{p} + \frac{1}{q} + \frac{1}{r} \bigg) + \bigg( \frac{1}{pq} + \frac{1}{pr} + \frac{1}{qr} \bigg) - \frac{1}{pqr} \right] \\[1ex] & = n \bigg( 1 - \frac{1}{p} \bigg) \bigg( 1 - \frac{1}{q} \bigg) \bigg( 1 - \frac{1}{r} \bigg). \tag*{$\myblue{\blacksquare}$} \end{align*}

$ $

참고. 위 사실을 일반화하면, 양의 정수 $n \geq 2$이 \[ n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} \] 와 같이 소인수분해된다고 할 때, $1$부터 $n$까지의 양의 정수 중 $n$과 서로소인 양의 정수의 개수는 \[ \varphi(n) = n \prod_{i=1}^{k} \bigg( 1 - \frac{1}{p_i} \bigg) \] 로 주어짐을 보일 수 있다. 위 식 우변의 $\varphi(n)$를 정수론에서는 오일러 피 함수_{(Euler's totient function)}라 부른다. $ $

$ $

예제 1.7.3.
Q. $1$부터 $180$까지의 양의 정수 중 $180$과 서로소인 양의 정수의 개수를 구하여라.
A. $180 = 2^2 \cdot 3^2 \cdot 5$이므로, 위 공식에 의해 \[ \varphi(120) = 120 \bigg( 1 - \frac{1}{2} \bigg) \bigg( 1 - \frac{1}{3} \bigg) \bigg( 1 - \frac{1}{5} \bigg) = 32. \tag*{$\myblue{\blacksquare}$} \]

$ $

예제 1.7.4.
Q. 방정식 $x_1 + x_2 + x_3 + x_4 = 15$의 음이 아닌 정수해 중에서 각 $x_i$가 $5$을 넘지 않는 해의 개수를 구하여라.
A. 먼저 $X$를 주어진 방정식의 음이 아닌 정수해의 집합이라 하면 \[ \abs{X} = {}_{4}H_{15} = \binom{18}{15} = 816. \] 이제 $i = 1,\ 2,\, 3,\, 4$에 대하여 집합 $A_i$를 주어진 방정식의 음이 아닌 정수해 중 $x_i \geq 6$인 해의 집합으로 정의하자. 우선 집합 $A_1$의 크기를 구하기 위해 $x_1 = y_1+ 6$이라 하면, $\abs{A_1}$의 값은 다음 방정식 \[ y_1 + x_2 + x_3 + x_4 = 9 \] 의 음이 아닌 정수해의 개수와 같다. 따라서 \[ \abs{A_1} = {}_{4}H_{9} = \binom{12}{9} = 220. \] 마찬가지 방법으로 \begin{align*} & \abs{A_1} = \abs{A_2} = \abs{A_3} = \abs{A_4} = {}_{4}H_{9} = 220, \\[1ex] & \abs{A_1 \cap A_2} = \cdots \abs{A_3 \cap A_4} = {}_{4}H_{3} = 20, \\[1ex] & \abs{A_1 \cap A_2 \cap A_3} = \cdots = \abs{A_2 \cap A_3 \cap A_4} = 0, \\[1ex] & \abs{A_1 \cap A_2 \cap A_3 \cap A_4} = 0 \end{align*} 을 얻는다. 따라서 포함배제의 원리에 의해 \begin{align*} \abs{A_1^c \cap A_2^c \cap A_3^c \cap A_4^c} & = \abs{X} - \abs{A_1^c \cup A_2^c \cup A_3^c \cup A_4^c} \\[1ex] & = 816 - \Big( 220 \cdot 4 - 20 \cdot 6 + 0 \cdot 4 - 0 \cdot 1 \Big) \\[1ex] & = 56. \tag*{$\myblue{\blacksquare}$} \end{align*}

$ $

예제 1.7.5.
Q. 두 집합 $X,\, Y$의 크기가 각각 $\abs{X} = n$, $\abs{Y} = m$로 주어졌을 때, 포함배제의 원리를 이용하여 $X$에서 $Y$로 가는 전사함수의 개수를 \[ \sum_{k=0}^{m} (-1)^k \binom{m}{k} (m-k)^n \] 으로 나타낼 수 있음을 증명하여라.
A. 먼저 모든 함수 $f : X \to Y$의 개수는 \[ m^n = \binom{m}{0} (m-0)^n \] 이다. 이제 각각의 $k = 1,\, 2,\, \ldots,\, m$에 대하여 \[ A_{k} = \set{f : X \to Y}{k \notin f(X)} \] 를 정의하자. 즉, $A_{k}$는 치역에 $k$가 포함되지 않는 함수들의 집합이다. 그러면 구하고자 하는 $Y$ 위로의 전사함수의 개수는 \[ \abs{A_1^c \cap A_2^c \cap \cdots \cap A_m^c} \] 로 나타낼 수 있다. 우선 임의의 $k$에 대하여 $\abs{A_k} = (m-1)^n$이므로 $I = \{1,\, 2,\, \ldots,\, m\}$이라 하면 \[ \sum_{\substack{J \subset I \\ \abs{J} = 1}} \bigg| \bigcap_{j \in J} A_j \bigg| = m (m-1)^n = \binom{m}{1} (m-1)^n \] 을 얻는다. 또한 임의의 $k \neq l$에 대하여 $\abs{A_k \cap A_l} = (m-2)^n$이므로 \[ \sum_{\substack{J \subset I \\ \abs{J} = 2}} \bigg| \bigcap_{j \in J} A_j \bigg| = \binom{m}{2} (m-2)^n \] 을 얻는다. 이와 같은 방법으로 모든 $1 \leq k \leq m$에 대하여 \[ \sum_{\substack{J \subset I \\ \abs{J} = k}} \bigg| \bigcap_{j \in J} A_j \bigg| = \binom{m}{k} (m-k)^n \] 가 성립함을 알 수 있다. 따라서 포함배제의 원리에 의해 \begin{align*} \abs{A_1^c \cap A_2^c \cap \cdots \cap A_m^c} & = m^n - \abs{A_1 \cup A_2 \cup \cdots \cup A_m} \\[1ex] & = m^n + \sum_{k=1}^{m} \sum_{\substack{J \subset I \\ \abs{J} = k}} (-1)^{k} \bigg| \bigcap_{j \in J} A_j \bigg| \\[1ex] & = \binom{m}{0} (m-0)^n + \sum_{k=1}^{m} (-1)^{k} \binom{m}{k} (m-k)^n \\[1ex] & = \sum_{k=0}^{m} (-1)^{k} \binom{m}{k} (m-k)^n. \tag*{$\myblue{\blacksquare}$} \end{align*}

$ $

참고. 두 집합 $X,\, Y$의 크기가 각각 $\abs{X} = n$, $\abs{Y} = m$로 주어졌을 때, $X$에서 $Y$로 가는 전사함수의 개수는 $m! S(n,\, m)$이라는 사실로부터, 제2종 스털링 수에 대한 일반항 \[ S(n,\, m) = \frac{1}{m!} \sum_{k=0}^{m} (-1)^{k} \binom{m}{k} (m-k)^n \] 을 얻을 수 있다. $ $

$ $

일대일대응 $\sigma : \{1,\, 2,\, \ldots,\, n\} \to \{1,\, 2,\, \ldots,\, n\}$ 중에서 \[ \sigma(k) \neq k \qquad (k = 1,\, 2 ,\, \ldots,\, n) \] 을 만족하는 $\sigma$를 크기가 $n$인 교란순열_{(derangement)}이라 하고. 크기가 $n$인 교란순열의 개수를 $D_n$으로 나타낸다.

$ $

정리 1.7.6. 교란순열의 일반항

음이 아닌 정수 $n$에 대하여, \[ D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}. \]

$ $

증명. $I = \{1,\, 2,\, \ldots,\, n\}$라 하고 $k = 1,\, 2,\, \ldots,\, n$에 대하여, 집합 \[ A_k = \set{\sigma}{\sigma(k) = k} \] 를 정의하자. 즉, $A_k$는 $\sigma(k) = k$로 고정하고 나머지 정수들을 무작위로 배열한 대응들의 집합과 같다. 그러므로 \[ \abs{A_1} = \abs{A_2} = \cdots = \abs{A_n} = (n-1)! \] 을 얻는다. 같은 방법으로 \begin{align*} & \abs{A_1 \cap A_2} = \cdots = \abs{A_{n-1} \cap A_n} = (n-2)! \\[1ex] & \abs{A_1 \cap A_2 \cap A_3} = \cdots = \abs{A_{n-2} \cap A_{n-1} \cap A_n} = (n-3)! \\[1ex] & \qquad\qquad\qquad \vdots \\[1ex] & \abs{A_1 \cap \cdots A_n} = 1 = 0! \end{align*} 을 각각 얻는다. 이제 포함배제의 원리에 의해서 \begin{align*} \abs{D_n} & = \abs{A_1^c \cap A_2^c \cap \cdots \cap A_n^c} \\[1ex] & = \abs{X} - \abs{A_1 \cup A_2 \cup \cdots \cup A_n} \\[1ex] & = n! - \sum_{k=1}^{n} \sum_{\substack{J \subset I \\ \abs{J} = k}} (-1)^{k+1} \bigg| \bigcap_{j \in J} A_j \bigg| \\[1ex] & = n! + \sum_{k=1}^{n} \sum_{\substack{J \subset I \\ \abs{J} = k}} (-1)^k (n-k)! \\[1ex] & = n! + \sum_{k=1}^{n} (-1)^k \binom{n}{k} (n-k)! \\[1ex] & = \sum_{k=0}^{n} (-1)^k \binom{n}{k} (n-k)! \\[1ex] & = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} \end{align*} 을 얻는다. $ $

$ $

정리 1.7.7. 교란순열의 점화식 1

음이 아닌 정수 $n$에 대하여, \[ D_n = (n-1)(D_{n-1} + D_{n-2}). \] 단, $D_0 = 1,\, D_1 = 0$으로 정의한다.

$ $

증명. 교란순열 $\sigma : \{1,\, 2,\, \ldots,\, n\} \to \{1,\, 2,\, \ldots,\, n\}$에 대하여 $\sigma(1) = k$라 가정하고, 두 가지로 경우를 나누어 생각해 보자.

• $\sigma(k) = 1$인 경우: 이 경우는 두 원소 $\{1,\, k\}$가 서로 맞교환된 경우이므로 나머지 $k-2$개 원소에 대한 교란순열의 개수를 구하면 충분하다. 즉, 이 경우 $D_{n-2}$가지 경우의 수가 나온다.
• $\sigma(k) \neq 1$인 경우: 이 경우 $k$는 $1$이 아닌 다른 원소에 대응되어야 하고, 나머지 $k-2$개 원소들도 각각 자기자신이 아닌 원소에 대응되어야 하므로, 결국 $k-1$개 원소에 대한 교란수열의 개수인 $D_{n-1}$가지 경우의 수가 나온다.

위 두 사건은 동시에 발생할 수 없으므로, 합의 법칙에 의해 총 경우의 수는 $D_{n-1} + D_{n-2}$이다. 이제 처음 가정에서 $k$가 가질 수 있는 값은 $2,\, 3,\, \ldots,\, n$의 총 $n-1$가지이므로, 곱의 법칙에 의해 \[ D_n = (n-1)(D_{n-1} + D_{n-2}) \] 를 얻는다. $ $

$ $

예제 1.7.8.
Q. 교란순열의 점화식과 일반항을 이용하여 $D_6$의 값을 구하여라.
A. 먼저 $D_0 = 1$, $D_1 = 0$으로 부터 점화식을 이용하면 \begin{align*} D_2 & = (2-1)(D_1 + D_0) = 1 \\[1ex] D_3 & = (3-1)(D_2 + D_1) = 2 \\[1ex] D_4 & = (4-1)(D_3 + D_2) = 9 \\[1ex] D_5 & = (5-1)(D_4 + D_3) = 44 \\[1ex] D_6 & = (6-1)(D_5 + D_4) = 265 \end{align*} 를 얻는다. 이번에는 일반항을 이용하면 \begin{align*} D_6 & = 6! \sum_{k=0}^{n} \frac{(-1)^k}{k!} \\[1ex] & = 6! \bigg( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - \frac{1}{5!} + \frac{1}{6!} \bigg) \\[1ex] & = 265. \tag*{$\myblue{\blacksquare}$} \end{align*}

$ $

정리 1.7.7. 교란순열의 점화식 2

음이 아닌 정수 $n$에 대하여, \[ n! = \sum_{k=0}^{n} \binom{n}{k} D_{k}. \]

$ $

증명. 위 식의 좌변은 모든 일대일대응 $\sigma : \{1,\, 2,\, \ldots,\, n\} \to \{1,\, 2,\, \ldots,\, n\}$의 개수이다. 이제 이 개수를 경우를 다음과 같이 나누어 생각해 보자. 각각의 $k = 0,\, 1,\, \ldots,\, n$에 대하여 정확히 $k$개의 숫자만 자기자신으로 대응시키고 나머지는 전부 다른 숫자에 대응시키는 일대일대응의 개수를 생각해 보면, 먼저 $n$개의 숫자 중에서 자기자신으로 대응될 $k$개의 숫자를 고르고, 나머지 $(n-k)$개의 숫자에 대한 교란순열을 생각하면 되므로 \[ \binom{n}{k} D_{n-k} \] 임을 알 수 있다. 따라서 \[ n! = \sum_{k=0}^{n} \binom{n}{k} D_{n-k} = \sum_{k=0}^{n} \binom{n}{n-k} D_{n-k} = \sum_{k=0}^{n} \binom{n}{k} D_{k} \] 를 얻는다. $ $

$ $