다음 정리는 두 사건 $\alpha,\, \beta$가 있을 때, 사건 $\alpha$ 또는 $\beta$가 일어나는 경우의 수를 나타낸다.

$ $

정리 1.1.1. 합의 법칙_{(rule of sum)}

두 집합 $A,\, B$에 대하여,

• 만약 $A \cap B = \emptyset$이면, $\abs{A \cup B} = \abs{A} + \abs{B}$.
• 일반적으로 $\abs{A \cup B} = \abs{A} + \abs{B} - \abs{A \cap B}$.

$ $

예제 1.1.2.
Q. $1$ 부터 $100$ 사이의 정수 중 $2$ 또는 $3$의 배수의 개수를 구하여라.
A. $A$와 $B$를 각각 $1$부터 $100$ 사이의 정수 중 $2$의 배수와 $3$의 배수를 모아 놓은 집합으로 정의하자. \[ A = \{2,\, 4,\, \ldots,\, 100\}, \quad B = \{3,\, 6,\, \ldots,\, 99\} \] 라 하면 $\abs{A} = 50$, $\abs{B} = 33$이다. 한편, $A \cap B$는 $1$ 부터 $100$ 사이의 정수 중 $6$의 배수를 모아 놓은 집합이므로 \[ A \cap B = \{6,\, 12,\, \ldots,\, 96\}, \] $\abs{A \cap B} = 16$이다. 따라서 \[ \begin{align*} \abs{A \cup B} & = \abs{A} + \abs{B} - \abs{A \cap B} \\[1ex] & = 50 + 33 - 16 \\[1ex] & = 67. \tag*{$\myblue{\blacksquare}$} \end{align*} \]

$ $

예제 1.1.3.
Q. $50$명이 정원인 수학과에서 $32$명이 해석학, $40$명이 대수학을 수강한다고 한다. 해석학과 대수학을 모두 수강하는 학생의 범위를 구하여라.
A. $X$를 전체집합, 그리고 $A$와 $B$를 각각 해석학을 수강하는 학생, 대수학을 수강하는 학생들의 집합이라고 정의하자. 그러면 문제의 조건에 의해 \[ \abs{X} = 50,\, \abs{A} = 32,\, \abs{B} = 40 \] 임을 알 수 있다. 한편, 임의의 집합 $A, B$에 대하여 다음 부등식이 성립한다. \[ \max \big\{ \abs{A},\, \abs{B} \big\} \leq \abs{A \cup B} \leq \abs{X}. \] 그러므로 \[ \begin{align*} 40 \leq \abs{A \cup B} \leq 50 \; & \implies 40 \leq \abs{A} + \abs{B} - \abs{A \cap B} \leq 50 \\[1ex] & \implies -32 \leq - \abs{A \cap B} \leq -22 \\[1ex] & \implies 22 \leq \abs{A \cap B} \leq 32. \tag*{$\myblue{\blacksquare}$} \end{align*} \]

$ $

세 집합 $A,\, B,\, C$에 대하여 다음과 같은 합의 법칙을 따른다. \begin{align*} \abs{A \cup B \cup C} & = \abs{A} + \abs{B} + \abs{C} \\[1ex] & \qquad - \big\{\! \abs{A \cap B} + \abs{A \cap C} + \abs{B \cap C} \!\big\} \\[1ex] & \qquad + \abs{A \cap B \cap C}. \end{align*} 위의 합의 법칙을 $n$개의 집합으로 일반화 한 것이 포함배제의 원리이다.

$ $

한편, $A$와 $B$를 모두 만족하지 '않는' 경우의 수는 전체 경우의 수에서 $A$ 또는 $B$를 만족하는 경우의 수를 제외하면 되므로 \begin{align*} \abs{A^{c} \cap B^{c}} & = \abs{(A \cup B)^{c}} \\[1ex] & = \abs{X - (A \cup B)} \\[1ex] & = \abs{X} - \abs{A \cup B} \\[1ex] & = \abs{X} - \big\{\! \abs{A} + \abs{B} - \abs{A \cap B} \!\big\} \end{align*} 를 얻는다.

$ $

예제 1.1.4.
Q. $1$부터 $100$ 사이의 정수 중 $6$과 서로소인 정수의 개수를 구하여라.
A. $6 = 2 \times 3$이므로, $2$의 배수도 아니고 $3$의 배수도 아닌 정수의 개수를 구하면 충분하다. \[ \abs{A^c \cap B^c} = \abs{X} - \abs{A \cup B} = 100 - 67 = 33. \tag*{$\myblue{\blacksquare}$} \]

$ $

예제 1.1.5.
Q. $1$부터 $100$ 사이의 정수 중 $30$과 서로소인 정수의 개수를 구하여라.
A. $30 = 2 \times 3 \times 5$이므로, $2$의 배수도, $3$의 배수도, 그리고 $5$의 배수도 아닌 정수의 개수를 구하면 된다. $A,\, B,\, C$를 각각 $1$부터 $100$ 사이의 정수 중 $2$의 배수, $3$의 배수, $5$의 배수인 집합으로 정의하면 \[ \begin{align*} & \abs{A} = 50,\, \abs{B} = 33,\, \abs{C} = 20, \\[1ex] & \abs{A \cap B} = 16,\, \abs{A \cap C} = 10,\, \abs{B \cap C} = 6, \\[1ex] & \abs{A \cap B \cap C} = 3 \end{align*} \] 을 각각 얻는다. 따라서 \[ \begin{align*} \abs{A^c \cap B^c \cap C^c} & = \abs{X} - \abs{A \cup B \cup C} \\[1ex] & = 100 - \big( 50 + 33 + 20 - 16 - 10 - 6 + 3 \big) \\[1ex] & = 26. \tag*{$\myblue{\blacksquare}$} \end{align*} \]

$ $

다음 정리는 두 사건 $\alpha,\, \beta$가 있을 때, 사건 $\alpha$가 일어나고 나서 사건 $\beta$가 일어나는 경우의 수를 나타낸다.

$ $

정리 1.1.6. 곱의 법칙_{(rule of product)}

두 집합 $A,\, B$에 대하여, \[ A \times B = \set{(a,\, b)}{a \in A,\, b \in B} \] 라 하자. 그러면 $\abs{A \times B} = \abs{A} \times \abs{B}$.

$ $

일반적으로 유한개의 집합 $A_1,\, A_2,\, \ldots,\, A_n$에 대하여 \[ \abs{A_1 \times A_2 \times \cdots \times A_n} = \abs{A_1} \times \abs{A_2} \times \cdots \times \abs{A_n}. \]

$ $

예제 1.1.7.
Q. 집합 $P = \{a,\, b,\, c\}$에서 $Q = \{0,\, 1\}$로 가는 모든 함수의 개수를 구하여라.
A. $A,\, B,\, C$를 각각 $a$에 대응되는 숫자, $b$에 대응되는 숫자, $c$에 대응되는 숫자들의 집합으로 정의하자. 그러면 $A = B = C = \{0,\, 1\}$이고 $\abs{A} = \abs{B} = \abs{C} = 2$이므로 \[ \abs{A \times B \times C} = \abs{A} \times \abs{B} \times \abs{C} = 2 \times 2 \times 2 = 8. \tag*{$\myblue{\blacksquare}$} \]

$ $

일반적으로 두 집합 $P,\, Q$에 대하여 $\abs{P} = m$, $\abs{Q} = n$이라 하면, $P$에서 $Q$로 가는 모든 함수의 개수는 $n^{m}$과 같다.

$ $

예제 1.1.8.
Q. $1$부터 $10000$ 까지의 모든 정수를 나열했을 때 나타나는 $5$의 개수를 구하여라.
A1. $1$부터 $10000$ 까지의 모든 정수를 나열했을 때 나타나는 $5$의 개수와 $0$부터 $9999$까지의 모든 정수를 나열했을 때 나타내는 $5$의 개수는 같다. 이제 \[ 0 \to 0000, \quad 12 \to 0012, \quad 301 \to 0301 \] 등으로 나타내면 \begin{align*} & \underline{\phantom{0}} \; \underline{\phantom{0}} \; \underline{\phantom{0}} \; 5 \quad \to \quad 1000\text{가지} \\[1ex] & \underline{\phantom{0}} \; \underline{\phantom{0}} \; 5 \; \underline{\phantom{0}} \quad \to \quad 1000\text{가지} \\[1ex] & \underline{\phantom{0}} \; 5 \; \underline{\phantom{0}} \; \underline{\phantom{0}} \quad \to \quad 1000\text{가지} \\[1ex] & 5 \; \underline{\phantom{0}} \; \underline{\phantom{0}} \; \underline{\phantom{0}} \quad \to \quad 1000\text{가지} \end{align*} 이므로 전체 경우의 수는 $4000$이다. $ $
A2. $0000$부터 $9999$까지의 수를 나열할 때 등장하는 모든 숫자의 개수는 \[ 4 \times 10000 = 40000 \] 이다. 이때, $0$부터 $9$까지 각각의 숫자는 동일한 횟수씩 사용되므로, 전체 수의 나열에서 등장하는 $5$의 개수는 $40000 / 10 = 4000$이다. $ $

$ $

예제 1.1.9.
Q. $1$부터 $10000$ 까지의 모든 정수 중 $5$를 포함하는 정수의 개수를 구하여라.
A1. 위 문제와 마찬가지로 $0000$ 부터 $9999$ 까지의 모든 정수 중 $5$를 포함하는 정수의 개수를 구해보자. \begin{align*} & \underline{\phantom{0}} \; \underline{\phantom{0}} \; \underline{\phantom{0}} \; 5 \quad \to \quad 1000 \times 4 = 4000\text{가지} \\[1ex] & \underline{\phantom{0}} \; \underline{\phantom{0}} \; 5 \; 5 \quad \to \quad 100 \times 6 = 600\text{가지} \\[1ex] & \underline{\phantom{0}} \; 5 \; 5 \; 5 \quad \to \quad 10 \times 4 = 40\text{가지} \\[1ex] & 5 \; 5 \; 5 \; 5 \quad \to \quad 1\text{가지} \end{align*} 따라서 포함배제의 원리에 의해 구하고자 하는 경우의 수는 \[ 4000 - 600 + 40 - 1 = 3439. \tag*{$\myblue{\blacksquare}$} \] A2. $1$부터 $10000$ 까지의 모든 정수 중 $5$를 포함하지 않는 정수의 개수를 구해보자. 그러기 위해서는 $0$부터 $9$ 까지의 숫자 중 $5$를 제외한 아홉개의 숫자를 각 자리에 배열하면 충분하다. 따라서 곱의 법칙에 의해 총 경우의 수는 \[ 9 \times 9 \times 9 \times 9 = 6561 \] 이다. 전체 정수 중 $5$를 포함하지 않는 정수의 개수를 제외하면 구하고자 하는 $5$를 포함하는 정수의 개수가 되므로, \[ 10000 - 6561 = 3439 \] 를 얻는다. $ $

$ $