조금은 느리게 살자: 순열(順列, Permutation)과 조합(組合, Combination)

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

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

1. 순열(permutation)

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

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

순열(順列, Permutation)은 이름 그대로 구별되는 사물을 순서대로 줄 세워서 나열한 경우의 수이다. 순열을 이해하기 위해 [그림 1]을 먼저 본다. 자리[위치]를 고려하여 숫자 $1,2,3,4$를 배치한 경우의 수는 얼마인가? 첫째 자리에는 4가지 경우, 둘째 자리에는 첫째 자리 숫자를 뺀 3가지 경우, 등등. 이렇게 헤아려가면 경우의 수는 $4 \times 3 \times 2 \times 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)의 군론에서 활짝 꽃이 피게 된다.

어떤 경우의 수가 순열 형태를 나타내는 예시는 아래와 같다.

서로 다른 혹은 구별되는 원소 $n$개 중에서 중복 없이 $r$개를 뽑아서 줄 세우기
숫자 $n, r$ 구별: $r \le n$이 성립해서 $r$은 $n$과는 독립적으로 $1$까지 줄어들 수 있음
서로 다른 원소 $n$개를 뽑아서 서로 다른 주머니 $r$에 넣기[∵ 서로 다른 $n$개에서 중복 없이 $r$개를 뽑아 줄 번호 매겨 세우고, 줄 번호를 주머니 종류로 연결하기]
구별되는 사람 $n$명에서 $r$명을 뽑아서 줄 세우기
서로 다른 원소 $r$개에서 서로 구별되는 $n$개로 가는 일대일 함수(一對一函數, one-to-one function) 혹은 단사 함수(單射函數, injective function) 관계[∵ 서로 다른 공역 원소 $n$개 중에서 중복 없이 $r$개를 뽑아서 정의역 원소 순서에 맞게 줄 세우기]

2. 조합(combination)

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

(2)

여기서 $n \ge r$이 성립한다. 식 (2)의 좌변항은 순열과 조합의 관계를 의미한다. $n$개 중에서 $r$개를 순서[위치, 자리]를 고려하지 않고 뽑은 후[${}_nC_r$] $r$개를 다시 줄을 세우면 당연히 순열[${}_nP_r$]과 결과가 같아져야 한다.

[그림 3] 같은 빨간색 네모를 순열한 경우(좌측)와 숫자 5개 중에서 3개를 뽑는 조합 경우(우측)

[그림 4] 같은 파란색 공과 빨간색 공을 순열한 경우

식 (2)를 좀더 쉽게 설명하면, 서로 다른 공이 $n$개 들어있는 큰 주머니에서 $r$개를 뽑아서 하나로 모은 경우의 수가 바로 조합 ${}_nC_r$이다. 예를 들어 [그림 3]의 우측을 본다. 숫자 5개에서 3개를 뽑아서 순서대로 나열하지 않고 그냥 모은 경우의 수를 보여준다. 조합 관점에서 ${}_5C_3$ = $5 \times 4 / 2$ = $10$이 나온다. 또 다른 측면으로 동일한 [그림 3]의 좌측 혹은 [그림 4]를 본다. 원소를 순서대로 나열하지만 동일한 원소가 있기 때문에 구별되지 않는 경우가 생긴다. 그래서 순열을 쓰지 못하고 조합을 사용해야 한다. [그림 3]의 좌측에서 원소 개수는 $5$개라서 순서대로 줄을 세우는 전체 경우의 수는 $5!$이 된다. 다만 동일한 모양을 가진 빨간색 네모와 흰색 네모가 각각 $3$개와 $2$개이므로, 구별되지 않는 경우를 제거하기 위해 $5! \mathop{/} (3! 2!)$ = ${}_5C_3$처럼 계산한다. 마찬가지로 [그림 4]에서는 구별되지 않는 파란색 공과 빨간색 공이 각각 $5$개와 $3$개라서 순서대로 나열하는 경우의 수는 $8! \mathop{/}{(5!3!)}$ = ${}_8C_5$가 된다. 개념을 더 넓혀서 같은 모양을 가진 사물이 $3$개 이상인 경우, 사물을 순서대로 나열하는 경우의 수도 조합을 확장해서 계산할 수 있다. 예를 들어, 서로 다른 $3$종류의 색깔을 가진 공이 각각 $k_1, k_2, k_3$개가 있을 때, 공을 순서대로 나열하는 경우의 수는 $n! \mathop{/} (k_1! k_2! k_3!)$이다. 여기서 전체 공의 개수는 $n$ = $k_1 + k_2 + k_3$이다. 조합을 확장한 $n! \mathop{/} (k_1! k_2! \cdots k_m!)$은 다항 계수(multinomial coefficient)라고 부른다. 여기서 $n$ = $k_1 + k_2 + \cdots + k_m$이다. 다항 계수는 여러 항의 곱셈을 전개한 관계인 다항 정리(multinomial theorem)를 유도할 때 쓰인다.

위에서 설명한 조합의 다양한 공식은 이항 정리(二項定理, binomial theorem)를 이용해 쉽게 구할 수 있다. 또한 조합의 역사는 고대 이집트부터 시작되기 때문에, 우리 예상과 다르게 매우 오래되었다. 근대 수학 기준으로 보면, 파스칼의 삼각형(Pascal's triangle)으로 유명한 파스칼Blaise Pascal(1623–1662)이 1654년파스칼 31세, 조선 효종 시절에 제안한 확률 이론에서 조합의 중요성을 날카롭게 강조했다[1].

경우의 수가 순열이 아닌 조합 형태를 띠는 예시도 소개한다.

서로 다른 혹은 구별되는 원소 $n$개 중에서 중복 없이 $r$개를 뽑아서 한 곳에 모으기
숫자 $n, r$ 구별: $r \le n$이 성립하므로 $r$은 $n$과는 독립적으로 $1$까지 줄어들 수 있음
같지 않은 원소 $n$개 중 $r$개를 선택해서 한 주머니에 넣기
구별되는 사람 $n$명에서 $r$명을 뽑아서 한 곳에 모으기
같은 혹은 구별되지 않는 원소 $r$개와 $n-r$개를 순서대로 나열하기: 구별되는 원소를 나열한 경우의 수는 $n!$이며, 원소가 구별되지 않도록 $r! (n-r)!$로 나눈 결과
원소가 $x_i < x_j$일 때 $f(x_i) < f(x_j)$를 만족하는 함수 관계; 반대로 $x_i > x_j$일 때 $f(x_i) > f(x_j)$인 함수 관계[∵ 서로 다른 공역 원소 $n$개 중에서 중복 없이 $r$개를 뽑아 대소 관계에 맞게 줄 세우기; 혹은 일대일 함수 개수를 ${}_nP_r$로 구한 후, 치역의 원소가 $f(x_i) < f(x_j)$를 만족하는 경우만 남도록 $r!$을 나누어줌(줄 세우지 않고 원소를 뽑기만 한 후에 순서에 맞게 줄 세우기)]

3. 중복 순열(permutation with repetition)

순열에서 경우의 수를 구할 때 중복이 허락된다면 중복 순열이 된다. 예를 들면 서로 다른 공이 $n$개 들어있는 큰 주머니에서 뽑은 공을 다시 넣으면서[혹은 중복을 허락해서] $r$개를 뽑아서 줄을 세운 경우의 수가 중복 순열(permutation with repetition) ${}_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$일 수 없다.

[그림 5] 함수로 생각한 중복 순열(원본 출처: wikipedia.org)

혹은 경우의 수를 따지기 위해 [그림 5]와 같은 함수(function) 관계를 생각해도 된다. 함수 정의에 의해 집합 $X$의 원소는 반드시 $Y$의 원소와 연결되어야 한다. 따라서 $X$의 원소 하나는 $Y$의 전체 원소 개수인 $n$개를 선택할 수 있다. 그래서 함수를 만드는 모든 경우의 수는 ${}_n \Pi_r$이 된다. 여기서 $n, r$은 각각 집합 $Y, X$의 원소 개수이다.

중복 순열로 계산하는 경우의 수는 다음과 같다.

서로 다른 $n$개 중에서 중복도 허용하며 $r$개를 뽑아서 줄 세우기; $n$개 중에서 선택되지 않는 경우도 존재
숫자 $n, r$ 구별: 강제로 $n$ = $1$로 만들기, 함수로 $r, n$을 연결하기; $n$은 사용되지 않을 수 있고 $r$은 반드시 쓰여야 함
서로 다른 원소 $r$개에서 서로 구별되는 $n$개로 가는 모든 함수 관계[∵ 서로 다른 공역 원소 $n$개에서 중복도 가능하게 정의역 원소 개수 $r$개만큼 뽑아서 줄 세우기]
구별되는 물건 $r$개를 다른 사람 $n$명에게 나누어주기; 물건을 받지 못하는 사람도 있음[∵ 서로 다른 $n$명에서 중복도 되게 $r$명을 뽑아서 물건 종류와 연결하기]

4. 중복 조합(combination with repetition)

조합에서 중복이 허락된다면 중복 조합(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이 된다. 혹은 [그림 5]와 같은 함수 관계를 만든다. 이때 중복 조합의 $X$ 원소는 서로 구별되지 않는다.

중복 순열과 다르게 중복 조합으로 만드는 경우의 수도 소개한다.

서로 다른 $n$개 중에서 중복도 허락하며 $r$개를 뽑아서 한 곳에 모으기; $n$개 중에서 선택되지 않는 경우도 존재
숫자 $n, r$ 구별: 강제로 $n$ = $1$로 만들기, 함수로 $r, n$을 연결하기; $n$은 사용되지 않을 수 있고 $r$은 반드시 쓰여야 함
동일한 원소 $r$개에서 서로 구별되는 $n$개로 가는 함수 관계[∵ 서로 다른 $n$개에서 중복도 되게 $r$개를 뽑아서 줄 세우지 않고 모아만 두고 같은 원소를 배정함]
같은 물건 $r$개를 서로 다른 사람 $n$명에게 나누어주기; 물건을 받지 못하는 사람도 있음[∵ 서로 다른 $n$명에서 중복도 되게 $r$명를 뽑아서 줄 세우지 않고 모아만 두고 같은 물건을 배정함]
방정식 $x_1 + x_2 + \cdots + x_n$ = $r$의 해, 여기서 $x_1, x_2, \cdots, x_n$은 음이 아닌 정수[∵ 서로 다른 변수 $x_i$에서 중복되게 $r$개를 뽑아서 숫자 1을 할당하기]
원소가 $x_i < x_j$일 때 $f(x_i) \le f(x_j)$를 만족하는 함수 관계; 반대로 $x_i > x_j$일 때 $f(x_i) \ge f(x_j)$인 함수 관계[∵ 서로 다른 공역 원소 $n$개에서 중복을 허락하며 $r$개를 뽑아서 모아둔 후, 순서에 맞게 공역 원소를 줄 세우기]

[참고문헌]

[1] B. Pascal, Traité du triangle arithmétique (Treatise on Arithmetical Triangle), 1654.

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