[이산수학] 이산확률과 경우의 수

 

이산확률과 경우의 수

---

1. 경우의 수(Counting)

경우의 수는 발생한 사건에서 가능한 모든 결과의 수를 세는 것을 의미합니다. 사건 A에서 발생하는 경우의 수를 N(A)할 때, 아래와 같은 법칙이 성립합니다.

연산법칙	관계
덧셈 법칙	N(A ∪ B) = N(A) + N(B) - N(A ∩ B)
곱셈 법칙	N(A × B) = N(A) × N(B)

 

2. 순열(Permutation)

순열은 순서를 고려하여 주어진 요소들을 배열하는 것을 의미합니다. 순열의 경우의 수는 P를 사용하며, n개의 요소들로부터 r개의 요소를 선택하여 순서에 맞추어 배열하는 경우의 수는 상황에 따라 다른 계산 법을 가지고 있으며, 아래처럼 표현합니다.

$$_{n}\mathrm{P}_{r}$$

 

2.1. 순열

n개의 요소에서 r개를 배열하는 경우의 수는 서로 다른 n개의 공을 r개 비어있는 칸에 1개씩 넣는 경우를 생각하면 이해가 쉽습니다. 첫 번째 칸에 공을 넣을 때는 n개의 공 선택권이 있습니다. 임의의 공을 첫 번째 칸에 배치한 뒤, 두 번째 칸에 새로운 공을 넣을 때는 이미 1개 공은 배치가 되었기 때문에 n-1개의 공 선택권이 있습니다. 즉, r번째 칸에 공을 넣을 때는 n-(r-1) 개의 공 선택권이 남아있게 됩니다. 각 칸에 공을 배치하는 행위를 개별적인 사건으로 생각하면 총 경우의 수는 모든 사건을 곱하여 계산할 수 있으며, 아래와 같은 수식이 성립합니다.

$$_{n}\mathrm{P}_{r} = n(n - 1)(n - 2) … (n - r + 1) = \frac{n!}{(n - r)!}$$

 

2.2. 중복순열(Repeated permutation)

그런데 만일 n개의 공을 r개 칸에 넣을 때, 꺼낸 공과 같은 공을 매번 채워주는 경우를 생각해 보면 경우의 수는 달라집니다. 공을 넣을 때마다 매번 n개의 공 선택권이 존재하게 됩니다. 즉, r번째 칸에 공을 넣을 때는 n개의 공 선택권이 존재합니다. 총 경우의 수는 아래와 같습니다.

$$n * n *…* n = n^r$$

 

2.3. 중복조합의 순열

이번에는 n개 공을 모두 사용하여 순열을 만드는 경우의 수를 생각해 보겠습니다. 즉, 앞선 경우에서 r = n인 상황인 겁니다. 그러면 총 순열의 경우의 수는 n!인 것을 쉽게 알 수 있습니다.

 

이때, 만약 n개의 공이 3종류만 존재하고 각각 p, q, r개의 공이 존재하는 경우라면 경우의 수는 달라집니다. 같은 종류의 공끼리는 순서가 바뀌어도 같은 순열이기 때문에 각 종류별로 순서가 바뀔 수 있는 경우의 수를 중복처리 해주어야 합니다. p개의 공이 배열될 수 있는 경우의 수는 p!이므로, 아래와 같은 공식이 성립합니다.

$$\frac{n!}{p!q!r!}$$

 

2.4. 원순열(Circular permutation)

n개의 공을 모두 사용하여 원형으로 배치하는 경우를 생각해 보겠습니다. 공을 원형으로 배치하게 되면 회전시켰을 때에도 같은 순열이기 때문에 회전할 수 있는 경우의 수를 중복처리 해주어야 합니다. 결국, 선형으로 배열한 순열의 경우의 수에서 n을 나눠주면 되므로 아래와 같은 공식이 성립합니다. 물론, n개 공이 중복조합인 경우에도 마찬가지입니다.

$$\frac{n!}{n} = (n - 1)!$$

 

3. 조합(Combination)

조합은 순서를 고려하지 않고 주어진 요소들을 배열하는 것을 의미합니다. 조합의 경우의 수는 C를 사용하며, n개의 요소들로부터 r개의 요소를 선택하여 순서 무관하게 배열하는 경우의 수는 아래처럼 표현합니다.

$$_{n}\mathrm{C}_{r}$$

 

조합의 경우의 수는 사실 순열 경우의 수에서 선택한 요소들이 순서를 의식하여 배치될 수 있는 경우의 수를 중복처리해 주면 됩니다. 따라서 아래와 같은 공식이 성립합니다.

$$_{n}\mathrm{C}_{r} = \frac{_{n}\mathrm{P}_{r}}{r!} = \frac{n!}{r!(n - r)!}$$

 

4. 이산확률(Discrete probability)

확률(Probability)은 어떤 사건들이 발생할 가능성을 수치적으로 나타낸 것이며, 이산확률은 이산적인 상황 즉 유한한 결과 개수를 갖는 상황에서 발생하는 사건들에 대한 확률을 의미합니다.

 

확률에서는 모든 결과들의 집합을 "표본공간(sample space)"라고 하며, 표본공간의 부분집합을 "사건(event)"이라고 합니다. 그리고 표본공간 S가 유한하며, S의 부분집합인 사건 A가 있을 때, 사건 A가 발생할 확률은 P(A)라고 하며, 아래 관계들이 성립합니다.

if ∀s ∈ S,
then 0 ≤ P(s) ≤ 1, P(S) = 1, P(∅) = 0

 

그리고 P(A)는 아래처럼 계산됩니다.

$$P(A) = \frac{|A|}{|S|}$$
$$P(A^c) = 1 - P(A)$$
$$P(A ∪ B) = P(A) + P(B) - P(A ∩ B)$$

 

5. 조건부 확률(Conditional probability)

조건부 확률은 동일 표본공간 내 2개 사건이 있을 때, 1개 사건이 일어났다는 가정 하에 나머지 1개 사건이 일어날 확률을 의미합니다. 사건 B가 일어났을 때 A가 일어날 조건부 확률은 P(A | B)라고 표현하며, 아래처럼 계산됩니다.

$$P(A | B) = \frac{P(A ∩ B)}{P(B)}$$

---

연관 게시글

---

참조

•