확률과통계

순열과 조합

경우의 수

Remark (Hakchin-경우의 수 도출 방법). 가능하면 함수로 생각해서 경우의 수를 계산하려 한다.

Definition 1 (사건) 어떤 실험이나 관찰에 의해 일어나는 결과

Definition 2 (경우의수) 어떤 사건이 일어날 수 있는 모든 경우의 가짓수

Theorem 1 (합의법칙) 두 사건 $A$ , $B$ 가 동시에 일어나지 않을 때, 사건 $A$ 가 일어나는 경우가 $m$ 가지, 사건 $B$ 가 일어나는 경우가 $n$ 가지이면 사건 $A$ [또는] 사건 $B$ 가 일어나는 경우의 수는 $m + n$

Theorem 2 (곱의법칙) 두사건 $A$ , $B$ 에 대하여 사건 $A$ 가 일어나는 경우가 $m$ 가지이고, 그 각각에 대하여 사건 $B$ 가 일어나는 경우가 $n$ 가지이면 두사건 $A$ , $B$ 가 동시에 일어나는 경우의 수는 $m n$

합의 법칙

$A \cap B = ϕ$ 일 때, $n (A \cup B) = n (A) + n (B)$
$A \cap B \neq ϕ$ 일 때, $n (A \cup B) = n (A) + n (B) - n (A \cap B)$

곱의 법칙

$n (A \times B) = n (A) \times n (B)$

순열

비중복순열

Definition 3 (비중복순열의 수와 $_{n} P_{r}$ ) 아래와 같다.

$_{n} P_{r}$ 은 비중복 순열이며, $n$ 개에서 $r$ 개를 일렬로 늘어놓는 경우의 수

Definition 4 ( $_{n} P_{r}$ 의 변형식과 기호의 정의) 아래와 같다.

$_{n} P_{r} = n! / (n - r)!$
$_{n} P_{n} = n!$
$0! = 1$
$_{n} P_{0} = 1$

중복순열

Definition 5 (중복순열의 수와 $_{n} Π_{r}$ ) 서로 다른 $n$ 개의 원소에서 중복을 허락하여 $r$ 개의 원소를 선택하여 일렬로 배열하는 경우의 수를 $n$ 개에서 $r$ 개 택한 중복순열¹이라 하고 이를 기호로 $_{n} Π_{r}$ 로 나타낸다.

Theorem 3 (중복순열 Theorem) $_{n} Π_{r} = n^{r}$

Proof. 어쩌구 저쩌구 …

여러가지 순열

원순열

같은 것이 있는 순열

완전순열=교란순열

자기가 자기 자신을 선택하지 못하는 순열

교란순열 (derangement)

조합

Remark. 순열은 순서가 있고, 조합은 순서가 없다.

비중복조합의 수

Definition 6 서로 다른 $n$ 개의 원에서 순서를 고려하지 않고 $r$ 개를 택할 때 이 $r$ 개로 이루어진 각각의 집합을 $n$ 개에서 $r$ 개를 택한 조합(Combination) 이라 하고 이 조합의 수를 $_{n} C_{r}$ 로 나타낸다. 또는 $(\binom{n}{r})$ 로 나타낸다.

공식과 기호의 정의

$_{n} C_{k} = \frac{_{n} P_{k}}{k!} = \frac{n!}{(n - k)! k!}$
$_{n} C_{k} =_{n} C_{n - k} (n \geq k)$
$_{n} C_{0} = 1$

Theorem 4

$_{n} C_{k} =_{n - 1} C_{k - 1} +_{n - 1} C_{k}$
$_{n} C_{k} = \frac{n}{k} \cdot_{n - 1} C_{k - 1}$
$k \cdot_{n} C_{k} = n \cdot_{n - 1} C_{k - 1}$
$_{n} C_{k} = \frac{n - k + 1}{k} \cdot_{n} C_{k - 1}$
$_{n} C_{k} = \frac{n}{n - k} \cdot_{n - 1} C_{k}$
$_{n} C_{k - 1} = \frac{k}{n - k + 1} \cdot_{n} C_{k}$
$_{n - 1} C_{k} = \frac{n - k}{n} \cdot_{n} C_{k}$
$_{n} P_{k} = n \cdot_{n - 1} P_{k - 1}$
$_{n} P_{k} = (n - k + 1) \cdot_{n} P_{k - 1}$
$_{n} P_{k} = k \cdot_{n - 1} P_{k - 1} +_{n - 1} P_{k} (w h e r e 1 \leq k < n)$

Definition 7 여러 개의 물건을 몇 개의 묶음으로 나누는 것을 분할이라 하고, 그 묶음을 나누어 주는 것을 분배라 한다.

중복조합

Definition 8 서로 다른 $n$ 개의 원소에서 중복을 허락하여 $r$ 개의 원소를 선택하는 경우의 수를 중복조합[^5]이라고 하고 이를 기호로 $_{n} H_{r}$ 로 나타낸다.

Theorem 5 $_{n} H_{r} =_{n - 1 + r} C_{r}$

Proof. $n$ 개에서 중복을 허락하여 $r$ 개를 택한 조합의 수는 $n - 1$ 개의 막대기와 $r$ 개의 구슬을 일렬로 늘어놓는 경우의 수와 같으므로 $H (n, r) = \frac{(n - 1 + r)!}{(n - 1)! r!} = \frac{(n - 1 + r)!}{(n - 1 + r - r)! r!} = C (n - 1 + r, r)$ ◻

Remark.

종류	경우의 수
모든함수	$Π (n, m)$
단사함수	$_{n} P_{m}$
전사함수	$S (m, n) \cdot_{n} P_{n}$
전단사함수	$_{n} P_{n}$
증가함수	$_{n} C_{m}$
단조증가함수	$_{n} H_{m}$

Exercise 1
집합 $X = {1, 2, 3, 4}$ 에 대하여 다음 조건을 만족시키는 함수 $f : X \to X$ 의 개수는?

Solution.

집합 $X$ 의 임의의 원소 $x$ 에 대하여 $f (x) \neq x$ 이다.

Solution.

$n (S) =_{4} P_{4} = 4! = 24$
$E : \forall x \in X, f (x) \neq x$
$E^{c} : \exists x \in X, f (x) = x$
$n (E^{c}) =_{4} C_{1} \cdot 2 +_{4} C_{2} \cdot 1 +_{4} C_{3} \cdot 0 +_{4} C_{4} \cdot 1 = 8 + 6 + 0 + 1 = 15$
$n (E) = 24 - 15 = 9$

Example 1

중복순열
- 1, 2, 3, 4 에서 중복을 허락하여 만들 수 있는 3자리의 정수 : $Π (4, 3)$ 서로 다른 4개의 숫자가 3번 선택당하는데 구분이 있다.
- 1, 2, 3, 4 에서 3명의 사람이 좋아하는 숫자를 기명 투표 : $Π (4, 3)$ 서로 다른 4개의 숫자가 3번 선택당하는데 구분이 있다.
- 1, 2, 3, 4 라는 상자에서 서로 다른 3개의 공을 넣는 방법의 수: $Π (4, 3)$ 서로 다른 4개의 상자가 3번 선택당하는데 구분이 있다.
중복조합
- 1, 2, 3, 4 에서 중복을 허락하여 3개의 숫자 선택 : $_{4} H_{3}$ 서로 다른 4개의 숫자가 3번 선택당하는데 구분이 없다.
- 1, 2, 3, 4 에서 3명의 사람이 좋아하는 숫자를 무기명 투표 : $_{4} H_{3}$ 서로 다른 4개의 숫자가 3번 선택당하는데 구분이 없다.
- 1, 2, 3, 4 라는 상자에서 동일한 3개의 공을 넣는 방법의 수: $_{4} H_{3}$ 서로 다른 4개의 상자가 3번 선택당하는데 구분이 없다.

Example 2

이항정리

Theorem 6 아래와 같다. $n$ 이 양의 정수일 때 $(a + b)^{n}$ 을 전개하면 다음과 같다.

$\begin{aligned} (a + b)^{n} \\ =_{n} C_{0} a^{0} b^{n} +_{n} C_{1} a^{1} b^{n - 1} +_{n} C_{2} a^{2} b^{n - 2} + . . . +_{n} C_{k} a^{k} b^{n - k} + . . . +_{n} C_{n - 1} a^{n - 1} b +_{n} C_{n} a^{n} b^{0} \\ =_{n} C_{0} a^{n} b^{0} +_{n} C_{1} a^{n - 1} b +_{n} C_{2} a^{n - 2} b^{2} + . . . +_{n} C_{k} a^{n - k} b^{k} + . . . +_{n} C_{n - 1} a b^{n - 1} +_{n} C_{0} a^{0} b^{n} \\ = \sum_{k = 0}^{n} C (n, k) a^{k} b^{n - k} \\ = \sum_{k = 0}^{n} C (n, k) a^{n - k} b^{k} \end{aligned}$

Theorem 7 이항정리를 이용하여 $(1 + x)^{n}$ 의 전개식 $(1 + x)^{n} =_{n} C_{0} +_{n} C_{1} x^{1} +_{n} C_{2} x^{2} + \dots +_{n} C_{k} x^{k} + \dots +_{n} C_{n} x^{n}$ 에서 다음과 같은 이항계수의 성질을 얻을 수 있다.

연속합 : $2^{n} =_{n} C_{0} +_{n} C_{1} +_{n} C_{2} + \dots +_{n} C_{n}$
교대합 : $0 =_{n} C_{0} -_{n} C_{1} +_{n} C_{2} + \dots + (- 1)_{n}^{n} C_{n}$
짝수합 = 홀수합 :

$\begin{aligned} 2^{n - 1} & =_{n} C_{0} +_{n} C_{2} +_{n} C_{4} + \dots +_{n} C_{l e} \\ =_{n} C_{1} +_{n} C_{3} +_{n} C_{5} + \dots +_{n} C_{l o} \end{aligned}$

절반합 :

$\begin{aligned} 2^{2 n} \\ =_{2 n + 1} C_{0} & +_{2 n + 1} C_{1} & +_{2 n + 1} C_{2} & + \dots & +_{2 n + 1} C_{n - 1} & +_{2 n + 1} C_{n} \\ =_{2 n + 1} C_{n + 1} & +_{2 n + 1} C_{n + 2} & +_{2 n + 1} C_{n + 3} & + \dots & +_{2 n + 1} C_{2 n} & +_{2 n + 1} C_{2 n + 1} \end{aligned}$

$n \cdot 2^{n - 1} = C (n, 1) + 2 \cdot C (n, 2) + 3 \cdot C (n, 3) + \dots + n \cdot C (n, n)$

Proof. 5번째 것에 대한 증명이다.

$(1 + x)^{n} =_{n} C_{0} +_{n} C_{1} x^{1} +_{n} C_{2} x^{2} + \dots +_{n} C_{k} x^{k} + \dots +_{n} C_{n} x^{n}$ 의 양변을 미분하여 증명
또는 $C (n, k) = \frac{n}{k} C (n - 1, k - 1) = C (n, k) = \frac{n (n - 1)}{k (k - 1)} C (n - 2, k - 2)$ 이므로 $k \cdot C (n, k) = n \cdot C (n - 1, k - 1)$ 을 이용하여 증명
즉,

$\begin{aligned} \sum_{k = 0}^{n} k \cdot_{n} C_{k} & = \sum_{k = 1}^{n} k \cdot_{n} C_{k} \\ = \sum_{k = 1}^{n} n \cdot_{n - 1} C_{k - 1} \\ = n (_{n - 1} C_{0} +_{n - 1} C_{1} + \dots +_{n - 1} C_{n - 1}) \\ = n \cdot 2^{n - 1} \end{aligned}$

분할

자연수의 분할

Ferrers’ diagram을 이용하면 자연수의 분할에 대한 성질을 쉽게 도출할 수 있다.

Definition 9 자연수 $n$ 을 자신보다 크지 않은 자연수 $n = n_{1} + n_{2} + n_{3} + \dots + n_{k} (n \geq n_{1} \geq n_{2} \geq n_{2} \geq n_{3} \geq \dots \geq n_{k} \geq 1)$ 와 같이 $n_{1}, n_{2}, n_{3}, \dots, n_{k}$ 의 합으로 나타내는 것을 자연수의 분할이라고 한다.

Definition 10 자연수 $n$ 을 $k (1 \leq k \leq n)$ 개의 자연수로 분할하는 경우의 수를 기호로 $P (n, k)$ 와 같이 나타낸다.

Theorem 8

$1 < k < n \Rightarrow P (n, k) = P (n - k, 1) + P (n - k, 2) + \dots + P (n - k, k)$
$1 < k < n \Rightarrow P (n, k) = P (n - 1, k - 1) + P (n - k, k)$
$P (n, k) = 0 (k > n)$

Theorem 9

$P (n, 1) = 1$
$P (n, 2) = [\frac{n}{2}]$
$\dots$
$P (n, n) = 1$
$P (n, n - 1) = 1 (n \geq 2)$
$P (n, n - 2) = 2 (n \geq 4)$
$P (n, n - 3) = 3 (n \geq 6)$
$P (n, n - 4) = 5 (n \geq 8)$

Definition 11 학진의 표기법이고 $Q (n, k)$ 은 $P (n, k)$ 와 같으며 단 $n$ 을 서로 다른 양의 정수로 분할하는 경우의 수

Definition 12 학진의 표기법이고 $R (n, k)$ 는 $n$ 을 $k$ 개 이하의 자연수로 분할하는 경우의 수

Example 3 $R (n, k) = P (n, 1) + P (n, 2) + \dots + P (n, k)$

Definition 13 학진의 표기법이고 $r (n, k)$ 는 $n$ 을 $k$ 이하의 자연수로 분할하는 경우의 수

Example 4 $n = n_{1} + n_{2} + n_{3} + \dots + n_{l} (k \geq n_{1} \geq n_{2} \geq n_{2} \geq n_{3} \geq \dots \geq n_{l} \geq 1)$

Definition 14 $R (n, k) = r (n, k)$

집합의 분할

Definition 15 원소의 개수가 $n$ 인 집합을 공집합이 아니면서 서로소인 $k (1 \leq k \leq n)$ 개의 부분집합으로 나누는 것을 집합의 분할이라 한다. 즉, 유한집합 A를 공집합이 아닌 k개의 부분집합 $A_{1}, A_{2}, \dots, A_{k}$ 으로 분할하면 $A_{i} \cap A_{j} = \emptyset (i, j = 1, 2, \dots, k \land i \neq j)$ $A_{1} \cup A_{2} \cup \dots \cup A_{k} = A$ 를 만족한다.

Definition 16 원소가 $n$ 개인 집합을 $k (1 \leq k \leq n)$ 개의 부분집합으로 분할하는 방법의 수를 기호로 $S (n, k)$ 와 같이 나타낸다.

Remark.

$S (n, k)$ 의 $S$ 는 스코틀랜드의 수학자 스털링(Stirling, J.: 1692 - 1770)의 이름 첫 글자이다.

Theorem 10

$p$ , $q$ , $r$ 가 모두 다른 수일 때, $C (n, p) \cdot C (n - p, q) \cdot C (r, r)$
$p$ , $q$ , $r$ 중 어느 두 수가 같을 때, $C (n, p) \cdot C (n - p, q) \cdot C (r, r) \cdot \frac{1}{2!}$
$p$ , $q$ , $r$ 의 세 수가 모두 같을 때, $C (n, p) \cdot C (n - p, q) \cdot C (r, r) \cdot \frac{1}{3!}$

Theorem 11 $1 < k < n \Rightarrow S (n, k) = S (n - 1, k - 1) + S (n - 1, k) \cdot k$

Proof. 원소의 개수가 $n$ 인 집합 ${1, 2, 3, \dots, n}$ 을 $k$ 개의 부분집합으로 분할하는 방법을 이용하여 위의 성질을 확인해 보자.

원소 $n$ 이 하나의 부분집합을 이루는 경우 (또는 임의의 한 원소가 단독으로 하나의 부분집합을 이루는 경우라 생각해도 된다.) $n$ 을 제외한 나머지 원소들로 구성된 부분집합 ${1, 2, 3, \dots, n - 1}$ 을 $k - 1$ 개로 분할하면 집합 ${n}$ 을 포함하여 전체집합은 $k$ 개로 분할이 된다. 이 경우 $k$ 개로 분할하는 경우의 수는 $S (n - 1, k - 1)$
원소 $n$ 이 다른 원소와 함께 1개의 부분집합을 이루는 경우 부분집합 ${1, 2, 3, \dots, n - 1}$ 을 $k$ 개의 집합으로 분할한 다음, $k$ 개의 부분집합중 하나를 택해 원소 $n$ 을 포함시키면 전체집합은 $k$ 개로 분할된다. 이 경우 $k$ 개로 분할하는 경우의 수는

$S (n - 1, k) \cdot k$ 여기서 $k$ 는 $n$ 을 포함시킬 부분집합을 고르는 경우의 수이기도 하다. 위로 부터 다음이 성립한다. $S (n, k) = S (n - 1, k - 1) + S (n - 1, k) \cdot k$

Corollary 1 $\begin{aligned} S (n, k) & = S (n - 1, k - 1) + S (n - 1, k) \cdot k \\ = S (n - 1, k - 1) \cdot k^{0} + S (n - 2, k - 1) \cdot k^{1} + S (n - 3, k - 1) \cdot k^{2} \\ + \dots + S (k - 1, k - 1) \cdot k^{n - k} \end{aligned}$

Theorem 12

$S (n, 1) = 1$
$S (n, 2) = \frac{2^{n} - 2}{2} = 2^{n - 1} - 1$
$S (n, n - 1) =_{n} C_{2}$
$S (n, n) = 1$
$S (n, k) = S (n - 1, k - 1) + S (n - 1, k) \cdot k$

Proof. 분할할 전체집합을 $U = {1, 2, \dots, n}$ 라고하자.

1개의 부분으로 분할하는 방법은 ${1, 2, \dots, n}$ 의 한 가지이다.
벤다이어그램을 결정하는 경우의 수를 구한다.

::: center :::
또는 다음과 같이 증명해 볼 수 있겠다. $S (17, 2)$ 은 원소가 17인 집합을 공집합이 아닌 2개의 서로소인 부분집합으로 분할하는 경우의 수이므로

$\begin{aligned} S (17, 2) \\ = C (17, 16) \cdot C (1, 1) + C (17, 15) \cdot C (2, 2) + C (17, 14) \cdot C (3, 3) + \dots + C (17, 9) \cdot C (8, 8) \\ = C (17, 1) + C (17, 2) + C (17, 3) + \dots + C (17, 8) \\ = (C (17, 0) + C (17, 1) + C (17, 2) + C (17, 3) + \dots + C (17, 8)) - C (17, 0) \\ = 2^{16} - 1 \end{aligned}$

집합 $A = {a_{1}, a_{2}, \dots, a_{n}}$ 에서 ${a_{1}, a_{2}} \cup {a_{3}} \cup \dots \cup {a_{n}}, {a_{1}, a_{3}} \cup {a_{2}} \cup \dots \cup {a_{n}}, \dots$ 의 경우를 말한다. 즉, $n$ 개의 원소 중에서 2개를 택하여 하나의 부분집합을 만들고, 나머지 $(n - 2)$ 개의 원소를 모두 자동으로 원소의 개수가 1개인 부분집합으로 만들면 된다. 따라서 $n$ 개의 원소 중에서 2개를 택하는 방법의 수와 같으므로 $S (n, n - 1) =_{n} C_{2}$ 이다.
$n$ 개의 부분으로 분할하는 방법은 ${1} \cup {2} \cup {3} \cup \dots \cup {n}$ 의 한 가지이다.
원소 $n$ 이 혼자서 1개의 부분집합을 이루는 경우 와 원소 $n$ 이 다른 원소와 함께 1개의 부분집합을 이루는 경우로 나누어 생각하며 증명한다.

◻

Remark.

다른 종류의 사탕 5개를 서로 다른 봉지 3개에 빈 봉지가 없도록 나누어 담는 경우
$S (5, 3) \cdot 3! = 25 \cdot 6 = 150$
다른 종류의 사탕 5개를 서로 다른 봉지 3개에 나누어 담는 경우
$_{3} Π_{5} = 3^{5} = 243$
같은 종류의 사탕 5개를 서로 다른 봉지 3개에 빈 봉지가 없도록 나누어 담는 경우
$_{3} H_{2} =_{4} C_{2} = 6$
같은 종류의 사탕 5개를 서로 다른 봉지 3개에 나누어 담는 경우
$_{3} H_{5} =_{7} C_{5} = 21$
같은 종류의 사탕 5개를 같은 모양의 봉지 3개에 빈 봉지가 없도록 나누어 담는 경우
$P (5, 3) = 2$
같은 종류의 사탕 5개를 같은 모양의 봉지 3개에 나누어 담는 경우
$P (5, 1) + P (5, 2) + P (5, 3) = 1 + 2 + 2 = 5$
다른 종류의 사탕 5개를 같은 모양의 봉지 3개에 빈 봉지가 없도록 나누어 담는 경우
$S (5, 3) = S (4, 2) + S (4, 3) \cdot 3 = 7 + 6 \cdot 3 = 7 + 18 = 25$
다른 종류의 사탕 5개를 같은 모양의 봉지 3개에 나누어 담는 경우
$S (5, 1) + S (5, 2) + S (5, 3) = 1 + 15 + 25 = 41$

Footnotes

repeated permutation↩︎