2010년 10월 15일 금요일

순열(順列, permutation)과 조합(組合, combination)


[경고] 아래 글을 읽지 않고 "순열과 조합"을 보면 바보로 느껴질 수 있습니다.


확률 이론에서 중요한 것은 경우의 수(number of cases)를 계산하는 것이다. 경우의 수를 계산할 때 유용하게 쓸 수 있는 것이 순열(順列, permutation)과 조합(組合, combination)이다.

1. 순열(permutation)
[그림 1] 1,2,3,4를 순열한 경우의 수(출처: wikimedia.org)

[그림 2] 파랑공, 빨강공, 초록공을 순열한 경우의 수(출처: wikimedia.org)

순열을 이해하기 위해 [그림 1]을 먼저 보자. 자리(위치)를 고려하여 숫자 1,2,3,4를  배치한 경우의 수는 얼마인가?
첫째자리에 4가지 경우, 둘째자리에 첫째자리 숫자를 뺀 3가지 경우, ...
이렇게 헤아려가면 경우의 수는 4×3×2×1 = 4! = 24가 되는 것을 알 수 있다. 여기서 !는 계승(階乘, factorial)을 의미한다.
마찬가지로 [그림 2]의 경우는 3! = 6이 된다.
그러면 일반적으로 $n$가지 종류에서 $r$개를 순서(위치, 자리)를 고려해서 뽑는 경우는 식 (1)로 정의한다.

                        (1)

여기서 $n \ge r$이 성립한다. 좀더 쉽게 설명하면 서로 다른 공이 $n$개 들어있는 큰주머니에서 $r$개를 뽑아서 줄을 세운 경우의 수가 순열 ${}_nP_r$이 된다.
별거 아니라고 생각할 수 있는 순열은 방정식의 가해성(solvability of equations)과 군론(group theory)으로 들어가는 핵심 열쇠이다. 순열이란 용어는 코쉬(Augustin-Louis Cauchy)가 정의했다. 순열 그 자체의 특성을 연구한 최초의 수학자는 당연히 코쉬이다. (이래서 최초가 중요하다.) 코쉬의 순열 개념은 갈루아(Évariste Galois)의 군론에서 활짝 꽃이 피게 된다.

2. 조합(combination)

순열을 이해하고 있으면 조합은 매우 쉽게 정의할 수 있다. 순열형태로 뽑아서 줄을 세우지 않고 모둠 형태로 한무더기로 모은 경우의 수가 조합이 된다.
예를 들면, [그림 1]에 있는 경우의 수(24가지)는 위치를 고려하고 있지만 이를 무시하고 모두 섞어버리면 가능한 경우의 수는 한 가지(1, 2, 3 ,4)로 줄어들게 된다.
이를 공식으로 표현하면 식 (2)가 된다.

                (2)

여기서 $n \ge r$이 성립한다.
식 (2)의 좌변항이 의미하는 것은 순열과 조합의 관계이다. $n$개 중에서 $r$개를 순서(위치, 자리)를 고려하지 않고 뽑은 후(${}_nC_r$) $r$개를 다시 줄을 세우면 당연히 순열(${}_nP_r$)과 결과가 같아져야 한다.
조합에 대한 다양한 공식들은 이항 정리(二項定理, binomial theorem)를 이용해 구할 수 있다.
식 (2)를 좀더 쉽게 설명하면 서로 다른 공이 $n$개 들어있는 큰주머니에서 $r$개를 뽑아서 하나로 모은 경우의 수가 조합 ${}_nC_r$이 된다.

3. 중복 순열(permutation with repetition)

순열에서 경우의 수를 구할 때 중복이 허락된다면 중복 순열이 된다. 예를 들면 서로 다른 공이 $n$개 들어있는 큰주머니에서 뽑은 공을 다시 넣으면서(or 중복을 허락해서) $r$개를 뽑아서 줄을 세운 경우의 수가 중복 순열 ${}_n \Pi_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$개를 뽑아서 모둠 형태로 한무더기로 모은 경우의 수가 중복 순열 ${}_nH_r$이 된다.
중복 조합 공식은 식 (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$이 되면 ${}_1H_r = {}_rC_r = 1$이 되므로 경우의 수는 $r$에 관계없이 1이 된다.

[다음 읽을거리]
1. 이항 정리
2. 행렬식
Enhanced by Zemanta

댓글 4개 :

  1. 비공개로 퍼갑니다. 감사합니다.

    답글삭제
  2. 여기 있는 내용은 출처를 밝히고 비영리 목적으로 쓰면 누구든 퍼갈 수 있습니다. 감사합니다.

    답글삭제
  3. 잘 읽어보고 갑니다 ^^*

    답글삭제

욕설이나 스팸글은 삭제될 수 있습니다. [전파거북이]는 선플운동의 아름다운 인터넷을 지지합니다.