확률과통계

순열과 조합

경우의 수

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\) 가 동시에 일어나는 경우의 수는 \(mn\)

합의 법칙

  • \(A \cap B = \phi\) 일 때, \(n(A \cup B) = n(A) + n(B)\)

  • \(A \cap B \neq \phi\) 일 때, \(n(A \cup B) = n(A) + n(B) - n(A \cap B)\)

곱의 법칙

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

순열

비중복순열

Definition 3 (비중복순열의 수와 \(_nP_r\)) 아래와 같다.

\(_nP_r\) 은 비중복 순열이며, \(n\) 개에서 \(r\) 개를 일렬로 늘어놓는 경우의 수

Definition 4 (\(_nP_r\) 의 변형식과 기호의 정의) 아래와 같다.

  • \(_nP_r = {n!}/{(n-r)!}\)

  • \(_nP_n = {n!}\)

  • \(0! = 1\)

  • \(_nP_0 = 1\)

중복순열

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

Theorem 3 (중복순열 Theorem) \[ _n\Pi_r = n^{r} \]

Proof. 어쩌구 저쩌구 …

여러가지 순열

원순열

같은 것이 있는 순열

완전순열=교란순열

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

조합

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

비중복조합의 수

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

공식과 기호의 정의

  1. \(_nC_k = \dfrac{_nP_k}{k!} = \dfrac{n!}{(n-k)!k!}\)

  2. \(_nC_k =_nC_{n-k} (n \geq k)\)

  3. \(_nC_0 = 1\)

Theorem 4  

  1. \(_nC_k =_{n-1}C_{k-1} +_{n-1}C_{k}\)

  2. \(_nC_k = \dfrac{n}{k} \cdot_{n-1}C_{k-1}\)

  3. \(k \cdot _nC_k = n \cdot_{n-1}C_{k-1}\)

  4. \(_nC_k = \dfrac{n-k+1}{k} \cdot_{n}C_{k-1}\)

  5. \(_nC_k = \dfrac{n}{n-k} \cdot_{n-1}C_{k}\)

  6. \(_{n}C_{k-1} = \dfrac{k}{n-k+1} \cdot _{n}C_{k}\)

  7. \(_{n-1}C_k = \dfrac{n-k}{n} \cdot_{n}C_{k}\)

  8. \(_nP_k = n \cdot_{n-1}P_{k-1}\)

  9. \(_nP_k = (n-k+1) \cdot_{n}P_{k-1}\)

  10. \(_nP_k = k \cdot_{n-1}P_{k-1} +_{n-1}P_{k}\ (where\ 1 \leq k < n)\)

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

중복조합

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

Theorem 5 \[ _nH_r =_{n-1+r}C_r \]

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

Remark.

종류 경우의 수
모든함수 \(\Pi(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 \rightarrow X\) 의 개수는?

Solution.

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

Solution.

  1. \(n( \mathcal{S} ) = _4 P_4 = 4! = 24\)

  2. \(E : \forall x \in X, f(x) \neq x\)

  3. \(E^c : \exists x \in X, f(x) = x\)

  4. \(n(E^c) = _4C_1 \cdot 2 +_4C_2 \cdot 1 + _4C_3 \cdot 0 +_4C_4 \cdot 1 = 8 + 6 + 0 + 1 = 15\)

  5. \(n(E) = 24 - 15 = 9\)

Example 1  

  • 중복순열

    • 1, 2, 3, 4 에서 중복을 허락하여 만들 수 있는 3자리의 정수 : \(\Pi(4,3)\) 서로 다른 4개의 숫자가 3번 선택당하는데 구분이 있다.

    • 1, 2, 3, 4 에서 3명의 사람이 좋아하는 숫자를 기명 투표 : \(\Pi(4,3)\) 서로 다른 4개의 숫자가 3번 선택당하는데 구분이 있다.

    • 1, 2, 3, 4 라는 상자에서 서로 다른 3개의 공을 넣는 방법의 수: \(\Pi(4,3)\) 서로 다른 4개의 상자가 3번 선택당하는데 구분이 있다.

  • 중복조합

    • 1, 2, 3, 4 에서 중복을 허락하여 3개의 숫자 선택 : \(_4H_3\) 서로 다른 4개의 숫자가 3번 선택당하는데 구분이 없다.

    • 1, 2, 3, 4 에서 3명의 사람이 좋아하는 숫자를 무기명 투표 : \(_4H_3\) 서로 다른 4개의 숫자가 3번 선택당하는데 구분이 없다.

    • 1, 2, 3, 4 라는 상자에서 동일한 3개의 공을 넣는 방법의 수: \(_4H_3\) 서로 다른 4개의 상자가 3번 선택당하는데 구분이 없다.

Example 2  

image

이항정리

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

\[ \begin{aligned} &(a+b)^n \\ &= _nC_0a^{0}b^{n} +_nC_1a^{1}b^{n-1} + _nC_2a^{2}b^{n-2} + ... +_nC_ka^{k}b^{n-k} + ... + _nC_{n-1}a^{n-1}b + _nC_na^{n}b^{0} \\ &= _nC_0a^{n}b^{0} +_nC_1a^{n-1}b + _nC_2a^{n-2}b^{2} + ... + _nC_ka^{n-k}b^{k} + ... + _nC_{n-1}ab^{n-1} + _nC_0a^{0}b^{n} \\ &= \sum_{k=0}^n C(n,k)a^kb^{n-k} \\ &= \sum_{k=0}^n C(n,k)a^{n-k}b^k \end{aligned} \]

Theorem 7 이항정리를 이용하여 \((1+x)^n\) 의 전개식 \[ (1+x)^n = _nC_0 +_nC_1x^{1} + _nC_2x^{2} + \cdots +_nC_kx^{k} + \cdots + _nC_nx^{n} \] 에서 다음과 같은 이항계수의 성질을 얻을 수 있다.

  1. 연속합 : \(2^n = _nC_0 +_nC_1 + _nC_2 + \cdots +_nC_n\)

  2. 교대합 : \(0 = _nC_0 -_nC_1 + _nC_2 + \cdots + (-1)^n_nC_n\)

  3. 짝수합 = 홀수합 :

\[ \begin{aligned} 2^{n-1} &= _nC_0 +_nC_2 + _nC_4 + \cdots +_nC_{le} \\ &=_nC_1 + _nC_3 +_nC_5 + \cdots + _nC_{lo} \end{aligned} \]

  1. 절반합 :

\[ \begin{aligned} &2^{2n} \\ &= _{2n+1}C_0 &+ _{2n+1}C_1 &+ _{2n+1}C_2 &+ \cdots &+ _{2n+1}C_{n-1} &+ _{2n+1}C_n \\ &= _{2n+1}C_{n+1} &+ _{2n+1}C_{n+2} &+ _{2n+1}C_{n+3} &+ \cdots &+ _{2n+1}C_{2n} &+ _{2n+1}C_{2n+1} \end{aligned} \]

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

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

  • \((1+x)^n = _nC_0 +_nC_1x^{1} + _nC_2x^{2} + \cdots +_nC_kx^{k} + \cdots + _nC_nx^{n}\) 의 양변을 미분하여 증명

  • 또는 \(C(n,k)=\dfrac{n}{k}C(n-1,k-1)=C(n,k)=\dfrac{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_nC_k &= \sum_{k=1}^n k \cdot_nC_k \\ &= \sum_{k=1}^n n \cdot_{n-1}C_{k-1} \\ &= n(_{n-1}C_0 + _{n-1}C_1 + \cdots +_{n-1}C_{n-1} ) \\ &= n \cdot2^{n-1} \end{aligned} \]

분할

자연수의 분할

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

Definition 9 자연수 \(n\) 을 자신보다 크지 않은 자연수 \[ n = n_1 + n_2 + n_3 + \cdots + n_k \text{ }(n \geq n_1 \geq n_2 \geq n_2 \geq n_3 \geq \cdots \geq n_k \geq 1) \] 와 같이 \(n_1, n_2, n_3, \cdots , n_k\) 의 합으로 나타내는 것을 자연수의 분할이라고 한다.

Definition 10 자연수 \(n\) 을 \(k \text{} (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) + \cdots + 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) = [\dfrac{n}{2}]\)

  • \(\cdots\)

  • \(P(n,n) = 1\)

  • \(P(n,n-1) = 1\ (n \ge 2)\)

  • \(P(n,n-2) = 2\ (n \ge 4)\)

  • \(P(n,n-3) = 3\ (n \ge 6)\)

  • \(P(n,n-4) = 5\ (n \ge 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)+ \cdots +P(n,k)\)

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

Example 4 \[n = n_1 + n_2 + n_3 + \cdots + n_l \text{ }(k \geq n_1 \geq n_2 \geq n_2 \geq n_3 \geq \cdots \geq n_l \geq 1)\]

Definition 14 \[R(n,k)=r(n,k)\]

집합의 분할

Definition 15 원소의 개수가 \(n\) 인 집합을 공집합이 아니면서 서로소인 \(k \text{} (1 \leq k \leq n)\) 개의 부분집합으로 나누는 것을 집합의 분할이라 한다. 즉, 유한집합 A를 공집합이 아닌 k개의 부분집합 \(A_1, A_2, \cdots , A_k\) 으로 분할하면 \[ A_i \cap A_j = \emptyset\ (i, j = 1,2, \cdots, k \wedge i \neq j) \] \[ A_1 \cup A_2 \cup \cdots \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 \dfrac{1}{2!}\)

  • \(p\) , \(q\) , \(r\) 의 세 수가 모두 같을 때, \(C(n,p) \cdot C(n-p,q) \cdot C(r,r) \cdot \dfrac{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, \cdots , n \}\) 을 \(k\) 개의 부분집합으로 분할하는 방법을 이용하여 위의 성질을 확인해 보자.

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

  • 원소 \(n\) 이 다른 원소와 함께 1개의 부분집합을 이루는 경우 부분집합 \(\{ 1,2,3, \cdots , 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 \\ &+ \cdots + S(k-1,k-1) \cdot k^{n-k} \end{aligned} \]

Theorem 12  

  1. \(S(n,1)=1\)

  2. \(S(n,2)= \dfrac{2^{n}-2}{2} = 2^{n-1} - 1\)

  3. \(S(n,n-1)= _nC_2\)

  4. \(S(n,n)=1\)

  5. \(S(n,k) = S(n-1,k-1) + S(n-1,k) \cdot k\)

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

  1. 1개의 부분으로 분할하는 방법은 \(\{1,2, \cdots, n\}\) 의 한 가지이다.

  2. 벤다이어그램을 결정하는 경우의 수를 구한다.

    ::: center image :::

  3. 또는 다음과 같이 증명해 볼 수 있겠다. \(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) + \cdots + C(17,9) \cdot C(8,8) \\ &= C(17,1) + C(17,2) + C(17,3) + \cdots + C(17,8) \\ &= ( C(17,0) + C(17,1) + C(17,2) + C(17,3) + \cdots + C(17,8)) - C(17,0) \\ &= 2^{16} - 1 \end{aligned} \]

  1. 집합 \(A=\{a_1,a_2, \cdots, a_n\}\) 에서 \(\{a_1,a_2\} \cup \{a_3\} \cup \cdots \cup \{a_n\}, \{a_1,a_3\} \cup \{a_2\} \cup \cdots \cup \{a_n\}, \cdots\) 의 경우를 말한다. 즉, \(n\) 개의 원소 중에서 2개를 택하여 하나의 부분집합을 만들고, 나머지 \((n-2)\) 개의 원소를 모두 자동으로 원소의 개수가 1개인 부분집합으로 만들면 된다. 따라서 \(n\) 개의 원소 중에서 2개를 택하는 방법의 수와 같으므로 \(S(n,n-1)= _nC_2\) 이다.

  2. \(n\) 개의 부분으로 분할하는 방법은 \(\{ 1 \} \cup \{ 2 \} \cup \{ 3 \} \cup \cdots \cup \{ n \}\) 의 한 가지이다.

  3. 원소 \(n\) 이 혼자서 1개의 부분집합을 이루는 경우 와 원소 \(n\) 이 다른 원소와 함께 1개의 부분집합을 이루는 경우로 나누어 생각하며 증명한다.

 ◻

Remark.

  • 다른 종류의 사탕 5개를 서로 다른 봉지 3개에 빈 봉지가 없도록 나누어 담는 경우

  • \(S(5,3) \cdot 3! = 25 \cdot 6 = 150\)

  • 다른 종류의 사탕 5개를 서로 다른 봉지 3개에 나누어 담는 경우

  • \(_3\Pi_5 = 3^5 = 243\)

  • 같은 종류의 사탕 5개를 서로 다른 봉지 3개에 빈 봉지가 없도록 나누어 담는 경우

  • \(_3H_2 =_4C_2 = 6\)

  • 같은 종류의 사탕 5개를 서로 다른 봉지 3개에 나누어 담는 경우

  • \(_3H_5 =_7C_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

  1. repeated permutation↩︎