확률이론에서 중요한 것은 경우의 수(number of cases)를 계산하는 것이다. 경우의 수를 계산할 때 유용하게 쓸 수 있는 것이 순열(順列, permutation)과 조합(組合, combination)이다.
1. 순열(permutation)
순열을 이해하기 위해 [그림 1]을 먼저 보자. 자리(위치)를 고려하여 숫자 1,2,3,4를 배치한 경우의 수는 얼마인가?
첫째자리에 4가지 경우, 둘째자리에 첫째자리 숫자를 뺀 3가지 경우, ...
이렇게 헤아려가면 경우의 수는 4×3×2×1 = 4! = 24가 되는 것을 알 수 있다. 여기서 !는 계승(階乘, factorial)을 의미한다.
마찬가지로 [그림 2]의 경우는 3! = 6이 된다.
그러면 일반적으로 n가지 종류에서 r개를 순서(위치, 자리)를 고려해서 뽑는 경우는 식 (1)로 정의한다.
(1)
여기서 n ≥ r이 성립한다. 좀더 쉽게 설명하면 서로 다른 공이 n개 들어있는 큰주머니에서 r개를 뽑아서 줄을 세운 경우의 수가 순열 nPr이 된다.
2. 조합(combination)
순열을 이해하고 있으면 조합은 매우 쉽게 정의할 수 있다. 순열형태로 뽑아서 줄을 세우지 않고 모둠 형태로 한무더기로 모은 경우의 수가 조합이 된다.
예를 들면, [그림 1]에 있는 경우의 수(24가지)는 위치를 고려하고 있지만 이를 무시하고 모두 섞어버리면 가능한 경우의 수는 한 가지(1, 2, 3 ,4)로 줄어들게 된다.
이를 공식으로 표현하면 식 (2)가 된다.
(2)
여기서 n ≥ r이 성립한다.
식 (2)의 좌변항이 의미하는 것은 순열과 조합의 관계이다. n개 중에서 r개를 순서(위치, 자리)를 고려하지 않고 뽑은 후(nCr) r개를 다시 줄을 세우면 당연히 순열(nPr)과 결과가 같아져야 한다.
조합에 대한 다양한 공식들은 이항정리(二項定理, binomial theorem)를 이용해 구할 수 있다.
식 (2)를 좀더 쉽게 설명하면 서로 다른 공이 n개 들어있는 큰주머니에서 r개를 뽑아서 하나로 모은 경우의 수가 조합 nCr이 된다.
3. 중복순열(permutation with repetition)
순열에서 경우의 수를 구할 때 중복이 허락된다면 중복순열이 된다. 예를 들면 서로 다른 공이 n개 들어있는 큰주머니에서 뽑은 공을 다시 넣으면서(or 중복을 허락해서) r개를 뽑아서 줄을 세운 경우의 수가 중복순열 nΠr이 된다.
(3)
뽑은 공은 다시 넣기 때문에 매번 뽑을 수 있는 공의 수는 n이 되어 식 (3)과 같은 공식화가 가능하다.
중복순열 문제를 풀 때 n과 r을 정하기 어려운 경우가 있다. 그 때는 강제적으로 n = 1이라 가정하면 된다. 그러면 1^r = 1이 되므로 가능한 경우의 수는 1이 된다. 즉, 두 숫자중에서 하나를 n = 1이라 가정했을 때 가능한 경우의 수가 1이 되는 숫자가 n이 된다.
예를 들어, 동전(앞면과 뒷면) 던지기를 5번하는 경우를 살펴보자. n = 2로 해야 하나 n = 5로 해야 하나?
강제적으로 동전이 앞면(n = 1)만 있다고 생각해보자. 그러면 가능한 경우의 수는 1이 되므로 동전이 가질 수 있는 값(앞면 혹은 뒷면: 2)이 n이 된다.
혹은 던진 회수를 강제로 n = 1이라 해보자. 동전은 앞면과 뒷면이 나올 수 있으므로 경우의 수는 2가 되어 던진 회수는 n이 될 수 없다.
4. 중복조합(combination with repetition)
조합에서 중복이 허락된다면 중복조합이 된다. 즉, 서로 다른 공이 n개 들어있는 큰주머니에서 뽑은 공을 다시 넣으면서(or 중복을 허락해서) r개를 뽑아서 모둠 형태로 한무더기로 모은 경우의 수가 중복순열 nHr이 된다.
중복조합 공식은 식 (2)의 좌변처럼 단순하게 만들 수 없다. 예를 들어 순서를 고려해(중복순열) 동전 던지기를 2번하면 HH, HT, TH, TT 4가지가 되지만 순서를 고려하지 않으면(중복조합) HH, HT, TT 3가지가 된다. 이는 식 (2)의 좌변 관계가 아니다.
중복조합 공식은 어떻게 만들어야 할까? 제일 쉬운 방법은 흑기사(or 조커)를 이용하는 것이다. 예를 들면 순서를 고려하지 않고 중복해서 동전을 2번 던지는 것은 중복을 허락하지 않고 동전이 H(앞면), T(뒷면), A(흑기사) 세가지 경우를 가지는 것과 동일하다. 그러면, HT, HA, TA 3가지가 우리가 찾는 답이다.
최종답을 낼 때는 중복조합 규칙(순서를 바꾸어 같은 경우는 삭제)을 만족하도록 흑기사 A를 H나 T로 교체해야 한다. 즉, HA → HH, HA → HT 두가지가 가능하나 이미 HT는 제시되어 있으므로 HA → HH로 택한다. 마찬가지로 TA → TT로 택한다. 그러면 답은 HT, HH, TT가 된다.
좀더 컴퓨터 친화적으로 이야기하면 HT, HA, TA의 둘째항을 T → H, A → T가 되도록 바꾸면 된다.
동전을 3번 던진다면 동전은 H(앞면), T(뒷면), A(흑기사1), B(흑기사2) 네가지 경우를 가진다고 할 수 있다. 그러면, HTA, HTB, HAB, TAB 4가지가 답이 된다.
흑기사 A, B를 H나 T로 바꾸면 HTA → HTH, HTB → HTT, HAB → HHH, TAB → TTT가 된다.
컴퓨터 친화적으로 쓰면 HTA, HTB, HAB, TAB의 둘째항은 T → H, A → T, 세째항은 A → H, B → T가 되도록 바꾸면 쉽게 답을 낼 수 있다.
이를 일반화해 공식으로 만들면 식 (4)가 된다.
(4)
중복조합과 유사하게 실제 문제에서는 n과 r을 정하기 어려우므로 강제적으로 n = 1이라 가정하는 방법을 쓰자. n = 1이 되면 1Hr = rCr = 1이 되므로 경우의 수는 r에 관계없이 1이 된다.
[다음 읽을거리]
1. 이항정리
2. 행렬식
출처 : http://ghebook.blogspot.kr/2010/10/permutation-combination.html
