원리 : 수형도, 합의 법칙, 곱의 법칙

수형도

수형도란 경우를 세는 방법의 하나로, `나무 모양의 그림'이라는 의미를 갖고 있습니다. 이름 그대로 나무가 가지를 뻗어나가는 것과 같은 모습으로 경우를 세어나갑니다.<sup>1</sup>우리가 경우의 수를 셀 때 `가짓수를 센다'의 가지는 결국 수형도의 나뭇가지의 수를 세는 것과 같은 것입니다. 그림 (a)는 동전을 두 번 던졌을 때, 전체 경우의 수 $4$가지를 수형도를 이용하여 그린 예입니다. 이때 수형도에서 가지가 갈라지는 지점을 마디라 부르도록 합시다. 그림 (a)에는 $3$개의 마디가 있음을 알 수 있습니다.

그림 (a)를 보면 가장 왼쪽 마디인 `전체 경우의 수'는 모든 수형도에 반드시 등장할 수밖에 없음을 알 수 있습니다. 따라서 그림 (b)와 같이 동일한 상황에서 가장 왼쪽 마디를 생략하고 그리면 마치 두 개의 수형도를 각각 그린 것과 같은 형태를 띱니다. 우리는 앞으로 수형도를 그릴 때 그림 (b)와 같이 불필요한 `전체 경우의 수'는 생략하고 그리기로 약속합시다.

수형도는 경우의 수의 처음이자 끝이라고 해도 과언이 아닙니다. 모든 경우의 수 문제는 수형도를 그리면 반드시 풀립니다. 특히 수능 주관식 문항은 답이 1000 미만이므로, 아무런 이론적 배경을 갖추지 못했더라도 시간 내에 수형도를 그린다면 반드시 맞힐 수 있습니다.²물론 이론상 그렇다는 것이고, 더 나은 방법이 있는데도 불구하고 모든 문제를 수형도로 풀이할 필요는 없습니다.

수형도를 잘 그리는 원칙

순서에 대한 규칙을 정하자

수형도를 혼동 없이 그리기 위해서는 일정한 규칙을 정하는 것이 좋습니다. 가령 그림 (a)와 같은 수형도에서는 항상 `앞'을 마디보다 위쪽에 적고, `뒤'를 마디보다 아래쪽에 적는 규칙을 따라 그리고 있습니다. 그림 (b)와 같이 순서에 일관성이 없다면, 수형도를 그리는 과정에서 몇 가지 경우를 빠뜨리거나 중복하여 적을 우려가 있습니다. 나중에 검토할 때에도 수형도에 틀린 부분이 있는지 검증하기 어려움을 겪을 수 있습니다.

첫 마디는 넓게 뻗어나가자

수형도의 특성상 뒤의 가지가 많이 퍼질 수밖에 없습니다. 그래서 그림 (a)와 같이 첫 마디에서 좁게 뻗어나가면 나중에 그림의 한가운데에서 위쪽 가지와 아래쪽 가지가 겹치게 됩니다. 그림 (b)와 같이 첫 마디에서 위아래로 멀리 뻗어나가면 이러한 문제를 예방할 수 있습니다.

원칙 적용의 예

[주사위를 던져 나온 눈의 수만큼 동전을 던진다. 이때 앞면이 나온 횟수가 $5$인 경우의 수는?]

주사위를 던져 나온 눈의 수가 $1$, $2$, $3$, $4$인 경우는 셀 필요가 없으므로, 수형도는 `첫 마디가 $5$인 경우'와 `첫 마디가 $6$인 경우' 두 개만 그리면 됩니다.

$5$에서는 앞앞앞앞앞 $1$가지, $6$에서는 앞앞앞앞앞뒤, 앞앞앞앞뒤앞, 앞앞앞뒤앞앞, 앞앞뒤앞앞앞, 앞뒤앞앞앞앞, 뒤앞앞앞앞앞 $6$가지가 있습니다. 따라서 구하는 경우의 수는 $1+6=7$가지입니다.

합의 법칙과 곱의 법칙 : 수형도를 그리는 데 활용되는 기본 원리

결국 합의 법칙과 곱의 법칙을 쓰는 것은, 수형도가 그려지는 구조를 파악하여 가급적 수형도를 덜 그리기 위한 것이라 생각할 수 있습니다. 수형도의 패턴이 반복되면 곱의 법칙을 이용해 수형도를 한 번만 그려 생략하고, 패턴이 다른 경우에는 어쩔 수 없이 각각의 수형도를 그린 후 합의 법칙으로 더합니다.

지금까지 배운 내용인 수형도, 합의 법칙, 곱의 법칙만을 이용하여 아래의 문제를 풀어봅시다.³같은 것이 있는 순열(같있순)은 아직 배우지 않았으므로, 같있순을 이용한 풀이는 뒤에서 다룰 것입니다.

[여섯 개의 자음 ㄱ, ㄱ, ㄴ, ㄴ, ㄷ, ㄷ을 일렬로 나열하여 문자열을 만든다. ㄱ은 ㄱ과 서로 이웃하지 않고, ㄴ은 ㄴ과 서로 이웃하지 않고, ㄷ은 ㄷ과 서로 이웃하지 않도록 배열된 문자열의 개수를 구하시오. ] 처음에 ㄱ, ㄴ, ㄷ으로 분류하여 수형도를 $3$개 그리겠다고 생각했다면, 그것만으로도 절반은 성공한 것입니다. 이때 ㄱ으로 시작하든, ㄴ으로 시작하든, ㄷ으로 시작하든, 이후 수형도의 구조가 같은지 곰곰이 생각해봅시다.

ㄱ의 입장에서 남은 것은 ㄱㄴㄴㄷㄷ이므로, 두 개씩 남은 ㄴ, ㄷ 중 하나를 선택하면 됩니다. ㄴ의 입장에서 남은 것은 ㄴㄷㄷㄱㄱ이므로, 두 개씩 남은 ㄱ, ㄷ 중 하나를 선택하면 됩니다. ㄷ의 입장에서 남은 것은 ㄷㄱㄱㄴㄴ이므로, 두 개씩 남은 ㄱ, ㄴ 중 하나를 선택하면 됩니다.

즉 서로 입장만 다를 뿐 완전히 동일한 상황임을 알 수 있습니다. 그래서 ㄱ으로 시작하는 경우의 수인 $n$을 구한 후, 여기에 $3$을 곱하면 전체 경우의 수인 $3n$을 구할 수 있습니다.⁴이것이 곧 곱의 법칙입니다.

여기까지 우리가 풀이하며 작성하는 식은 $3\times$입니다.

이제 ㄱ에만 집중하여 수형도를 그려나가봅시다. 앞서 말한 것과 같은 원리로, ㄴ을 고르든 ㄷ을 고르든 뒤의 수형도의 구조가 동일합니다. 따라서 ㄱ-ㄴ 이후만 그려나가면 됩니다. 여기까지 우리가 풀이하며 작성하는 식은 $3\times 2\times$입니다.

그런데 ㄱ-ㄴ-ㄱ과 ㄱ-ㄴ-ㄷ은 상황이 달라집니다. ㄱ-ㄴ-ㄱ에서는 ㄱ이 이미 다 쓰여 ㄴㄷㄷ만 남고, ㄱ-ㄴ-ㄷ은 ㄱ,ㄴ,ㄷ이 하나씩 남아 있는 상황이기 때문입니다. 따라서 이런 경우는 각각의 경우의 수인 $a$, $b$를 구한 후 더하여야 합니다.⁵이것이 곧 합의 법칙입니다. 여기까지 우리가 풀이하며 작성하는 식은 $3\times2\times\left(\qquad + \qquad \right)$입니다. 더하기의 왼쪽에는 $a$의 값을, 더하기의 오른쪽에는 $b$의 값을 적으면 됩니다.

이제 $a$를 구하기 위해 ㄱ-ㄴ-ㄱ를 마저 그려봅시다. ㄱ-ㄴ-ㄱ-ㄴ-ㄷ-ㄷ는 ㄷ끼리 이웃하여 문제의 조건에 위배되므로 세지 않습니다. ㄱ-ㄴ-ㄱ-ㄷ-ㄴ-ㄷ는 문제의 조건을 만족시킵니다.⁶여기서 ㄱ-ㄴ-ㄱ-ㄷ-ㄷ-ㄴ은 왜 그리지 않았는지 의문이 들 수 있습니다. 앞서 다룬 예제 $1$에서 주사위의 눈이 $1$, $2$, $3$, $4$가 나온 경우를 그리지 않은 것처럼, 확실하게 조건에 위배되므로 해당 경우는 그리지 않았습니다. 따라서 $a=1$입니다.

이제 $b$를 구하기 위해 ㄱ-ㄴ-ㄷ를 마저 그려봅시다. ㄱ-ㄴ-ㄷ-ㄱ와 ㄱ-ㄴ-ㄷ-ㄴ는 뒤의 수형도의 구조가 같습니다. 따라서 ㄱ-ㄴ-ㄷ-ㄱ만 풀이하고 $2$를 곱하면 $b$를 구할 수 있습니다. ㄱ-ㄴ-ㄷ-ㄱ에서는 ㄱ-ㄴ-ㄷ-ㄱ-ㄴ-ㄷ와 ㄱ-ㄴ-ㄷ-ㄱ-ㄷ-ㄴ의 $2$가지가 있으므로, $b=2\times2$입니다.

따라서 최종적으로 정답은 $3\times2\times\left( \:\: 1 \:\:+\:\: 2\times 2 \:\: \right) = 30$이 됩니다.

마치며

이에 더하여, 앞으로 다룰 여러 가지 순열과 조합 공식들은 자주 나오는 수형도를 그리지 않고도 한 방에 구하는 테크닉일 뿐입니다. 결국 이러한 테크닉을 적재적소에 활용한다면, 수형도를 그리지 않고도 수형도의 가짓수를 알 수 있을 것입니다.

자, 이제는 이 단원을 시작하며 말했던 아래의 문장이 다시금 와닿을 것입니다.

경우의 수 단원의 실력은 `수형도를 얼마나 잘 그리는 지'에 달려 있습니다. 그런데 역설적이게도, 수형도를 잘 그릴 수 있는 실력을 갖추면, 수형도를 간소하게 그리거나, 수형도를 전혀 그리지 않고도 경우의 수 문제를 풀 수 있게 됩니다.

1. 1. 우리가 경우의 수를 셀 때 `가짓수를 센다'의 가지는 결국 수형도의 나뭇가지의 수를 세는 것과 같은 것입니다.
2. 2. 물론 이론상 그렇다는 것이고, 더 나은 방법이 있는데도 불구하고 모든 문제를 수형도로 풀이할 필요는 없습니다.
3. 3. 같은 것이 있는 순열(같있순)은 아직 배우지 않았으므로, 같있순을 이용한 풀이는 뒤에서 다룰 것입니다.
4. 4. 이것이 곧 곱의 법칙입니다.
5. 5. 이것이 곧 합의 법칙입니다.
6. 6. 여기서 ㄱ-ㄴ-ㄱ-ㄷ-ㄷ-ㄴ은 왜 그리지 않았는지 의문이 들 수 있습니다. 앞서 다룬 예제 $1$에서 주사위의 눈이 $1$, $2$, $3$, $4$가 나온 경우를 그리지 않은 것처럼, 확실하게 조건에 위배되므로 해당 경우는 그리지 않았습니다.