경우의 수

32장짜리 카드 한 벌에서 카드 다섯 장을 고르는 방법이 몇 가지인지 알아야 한다고 하자. 이런 문제를 다루는 분야가 경우의 수(조합론)이다. 경우의 수에는 합의 법칙과 곱의 법칙이라는 두 가지 기본 법칙이 있다. 다른 모든 방법은 이 기본 원리를 넓힌 것일 뿐이다.

합의 법칙

합의 법칙은 아주 간단하다. 공통인 원소가 없는 두 집합 A, B가 있을 때, 합집합 A ∪ B에서 원소 하나를 고르는 방법의 수는 |A| + |B|, 즉 두 집합의 원소 개수의 합과 같다. (여기서 |A|는 집합 A의 원소의 개수로, 한국의 교과서에서는 n(A)로 쓴다.)

쉬운 예부터 보자. 빨간 공 6개와 파란 공 8개가 있다. 이 공들을 상자 하나에 모두 넣는다. 공을 하나 뽑을 때 경우의 수는 모두 몇 가지일까? 처음에 빨간 공의 집합이 있었고, 이를 집합 A라고 하자. 그리고 파란 공의 집합을 B라고 하자. 두 집합은 서로소, 즉 같은 공이 하나도 없다. 공을 하나 뽑으려는 것이므로 모두 |A| + |B| = 6 + 8 = 14가지이다. 이것으로 끝이다.

곱의 법칙

이번에도 두 집합 Z와 M이 있다. 집합 Z에는 여자 세 명, 집합 M에는 남자 네 명이 있다. 이 두 집합에서 남자와 여자의 쌍을 몇 가지 만들 수 있을까? 여자 한 명을 골라 남자 한 명을 짝지어 주는 것이다. 쌍의 개수는 다음과 같이 센다. 여자 한 명, 영희를 골라서 남자를 차례로 모두 짝지어 본다. 그러면 영희에게 짝지을 수 있는 남자가 모두 4명이므로 서로 다른 쌍이 4개 생긴다. 나머지 두 여자도 똑같이 하면 각각 쌍이 4개씩 더 생긴다. 이것으로 끝이다. 쌍은 모두 4 + 4 + 4 = 12개이다.

실제로는 무엇을 한 것일까? 두 집합의 원소 개수를 곱했다. 여자 3명과 남자 4명이 있었으므로 쌍의 개수는 모두 3 · 4 = 12이다. 그래서 곱의 법칙이라고 한다. 두 집합에서 쌍을 만들 때는 한 집합의 원소의 개수에 다른 집합의 원소의 개수를 곱하기만 하면 된다.

정말 그런지 확인해 보자. 다음은 여자 3명과 남자 4명으로 만들 수 있는 모든 쌍이다. 각 행은 여자 한 명의 경우이고, 각 열은 남자 한 명의 경우이다. 행이 세 개, 열이 네 개이므로 모두 행의 수 · 열의 수가지이다.

$$\begin{array}{rcl}& & (Z_1,M_1),(Z_1,M_2),(Z_1,M_3),(Z_1,M_4),\\ & & (Z_2,M_1),(Z_2,M_2),(Z_2,M_3),(Z_2,M_4),\\ & & (Z_3,M_1),(Z_3,M_2),(Z_3,M_3),(Z_3,M_4)\end{array}$$

풀이가 있는 예제

1. 두 자리 수는 모두 몇 개일까? 두 자리 수는 어떻게 생겼을까? 첫째 자리에는 숫자 1, …, 9 가운데 하나가 오고, 둘째 자리에는 0도 올 수 있으므로 0, …, 9 가운데 하나가 온다. 첫 번째 집합에는 숫자가 9개, 두 번째 집합에는 10개 있다. 곱의 법칙을 쓰면 최종 결과 9 · 10 = 90을 얻는다.

• 같은 숫자가 두 번 나오지 않는 세 자리 수는 모두 몇 개일까? 첫째 자리에는 이번에도 숫자 아홉 개가 올 수 있다. 수는 0으로 시작할 수 없다. 둘째 자리에는 0을 포함한 모든 숫자가 올 수 있지만 첫째 자리의 숫자는 올 수 없으므로, 숫자 10개에서 1을 뺀다(예를 들어 세 자리 수가 4로 시작하면 둘째 자리에는 4가 올 수 없다. 그러면 수 전체에 4가 두 번 나오기 때문이다). 셋째 자리에도 모든 숫자가 올 수 있지만 첫째 자리나 둘째 자리의 숫자는 올 수 없다. 이유는 앞과 같다. 첫째 자리가 4이고 둘째 자리가 7이면 셋째 자리에는 {0, …, 9} ∖ {4, 7}의 숫자 가운데 하나를 넣을 수 있다. 숫자 10개에서 2를 빼야 한다. 이제 곱하기만 하면 된다. 9 · 9 · 8 = 648이다. 따라서 이런 수는 모두 648개이다.
• 보통의 주사위를 두 번 잇달아 던진다. 나올 수 있는 결과는 몇 가지일까? 첫 번째 던질 때 주사위에서 나올 수 있는 결과는 6가지이다. 두 번째 던질 때도 마찬가지이므로 경우의 수는 모두 6 · 6 = 36이다.
• 주사위를 두 번 잇달아 던진다. 첫 번째에 짝수가 나왔다면 나올 수 있는 결과는 몇 가지일까? 첫 번째에는 짝수, 즉 2, 4, 6 가운데 하나가 나왔으므로 모두 3가지이다. 두 번째에는 어떤 수든 나올 수 있으므로 모두 3 · 6 = 18가지이다.