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(1789–1857)가 정의했다. 순열 그 자체의 특성을 연구한 최초의 수학자는 당연히 코쉬이다.[이래서 최초가 중요하다.] 코쉬의 순열 개념은 갈루아Évariste Galois(1811–1832)의 군론에서 활짝 꽃이 피게 된다.


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$개 들어있는 큰 주머니에서 뽑은 공을 다시 넣으면서[혹은 중복을 허락해서] $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$개 들어있는 큰 주머니에서 뽑은 공을 다시 넣으면서[혹은 중복을 허락해서] $r$개를 뽑아서 모둠 형태로 한무더기로 모은 경우의 수가 중복 순열 ${}_nH_r$이 된다. 중복 조합 공식은 식 (2)의 좌변처럼 단순하게 만들 수 없다. 예를 들어 순서를 고려해[중복 순열] 동전 던지기를 2번하면 HH, HT, TH, TT로 4가지가 되지만 순서를 고려하지 않으면[중복 조합] HH, HT, TT로 3가지가 된다. 이는 식 (2)의 좌변 관계가 아니다. 중복 조합 공식은 어떻게 만들어야 할까? 제일 쉬운 방법은 흑기사[혹은 조커]를 이용하기이다. 예를 들면 순서를 고려하지 않고 중복해서 동전을 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. 행렬식

댓글 4개 :

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

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

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

    답글삭제

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