수형도 그리기

순열과 조합을 배워도 경우의 수를 세는 일은 쉽지 않다. 경우의 수를 세는 가장 좋은 방법은 수형도(tree)를 그려서 모두 적어보는 것이다. 수형도는 나뭇가지 모양 그림이란 뜻이다. 요즘엔 한자를 아는 사람이 많지 않아서 수형도보다 그냥 트리라고 불러야 뜻이 더 쉽게 전달되는 느낌이다. 수형도는 확률과 통계, 컴퓨터 공학에도 많이 나온다.

$A,B,C,D$가 쓰인 카드를 일렬로 나열하는 경우의 수는 $4!=24$이다. 귀찮지만 모두 적었다. 자연스럽게 사전식으로 나열해야 계산하기 편리함을 알 수 있다. 생각나는 대로 마구 적으면 중간에 빠진 것을 찾아내기 어렵다.

수형도에는 순서가 정해진 네 자리에 문자를 잇달아 놓는 사건이므로 곱의 법칙에 따라 $4\times 3 \times 2 \times 1$임이 확실하게 드러난다. 

자연스럽게 서로 다른 $n$개를 일렬로 세우는 경우의 수는 $n!$임을 알 수 있다. 순열은 자연수로 생각하면 편하다. 서로 다른 $n$개의 자연수로 만들 수 있는 $n$자리 자연수로 생각하면 쉽게 이해할 수 있다. $n!$에서 많을 것을 이끌어 낼 수 있다.

같은 것이 있는 순열

서로 다른 것을 늘어놓는 순열을 이해했다면 같은 것이 들어 있는 순열도 생각해 보자.

문제 $A,B,C,C$을 일렬로 늘어놓는 방법은 모두 몇 가지인가?

물론 수형도를 새로 그려도 되지만 위에 그린 그림에서 $D$를 $C$로 바꾼다고 생각해 보자. 색깔을 넣어 보았다.

$ABCD$와 $ABDC$처럼 $C$와 $D$가 자리를 바꾼 것은 같은 것이 된다. 따라서 $4!/2=12$임을 쉽게 알 수 있다.

$$ABCC, \,\,ACBC,\,\, ACCB, \,\,BACC, \,\,BCAC, \,\,BCCA,$$

$$CABC,\,\,CACB,\,\,CBAC,\,\,CBCA,\,\,CCAB,\,\,CCBA$$

당연히 $ABCC$에 대한 수형도를 그려서 생각해도 된다. 하지만 개수가 많아지면 수형도만으론 어렵다. 위와 같이 모두 다르다고 생각한 순열에서 구별이 사라져 같아지는 비율을 따져야 일반화할 수 있다.

여기에 $B$를 $A$로 바꿔 $AACC$를 일렬로 늘어놓는 방법을 생각하면 $12/2=6$임을 쉽게 알 수 있다. 사전식으로 나열하면 아래와 같다.

$$AACC, \,\,ACAC, \,\,ACCA, \,\,CAAC, \,\,CACA,\,\,CCAA$$

순서가 있는 경우의 수가 없을 때보다 크지만 세기는 쉬울 때가 있다. $n$개 가운데 같은 것이 있는 순열의 수는 모두 다른 것의 순열의 수인 $n!$과 정비례한다. 먼저 $n!$을 같은 것이 자리를 바꾸는 순열의 수로 나누어 순서를 없애주면 된다.

$n$개 중에 같은 것이 각각 $p,q,\cdots r$개 씩 있는 것을 일렬로 나열하는 순열의 수는

$$\frac{n!}{p!q!\cdots r!}\,\,\quad( p+q+\cdots+r=n)$$

같은 것이 두 종류로 각각 $r$개와 $n-r$개라면 이는 조합의 수와 같다.

$$\frac{n!}{r!(n-r)!}={}_n C_r ={}_n C_{n-r}$$

문제 아래에 있는 붉은 공 2개, 푸른 공 3개를 일렬로 늘어놓는 경우의 수를 구하여라.

풀이 먼저 붉은 공은 $1,2$, 푸른 공은 $3,4,5$로 번호를 써서 구별한다고 하자. $1,2,3,4,5$를 일렬로 늘어놓은 순열의 수는 $5!$이다. 

푸른 공에 있는 번호를 지운다면 녹색 사각형 안에 있는 순열인 $3!$가지는 모두 같은 것이 된다. 따라서 $\displaystyle{\frac{5!}{3!}}$

마찬가지로 붉은 공에 있는 번호를 지우면 순열의 수는 다시 $\displaystyle{\frac{1}{2!}}$이 되므로

$$\frac{5!}{3!\times2!}=10$$

5명의 지원자에게 공을 나누어 줄 때, 붉은 공은 합격으로 푸른 공은 불합격으로 생각하면 이 순열의 수는 ${}_5 C_2$ 또는 ${}_5 C_3$으로 생각할 수 있다.

특정한 조건이 있는 순열

특정한 이들이 이웃하거나 이웃하지 않도록 하는 조건이 추가된 순열도 있다.

예제 남학생 3명과 여학생 4명이 일렬로 늘어설 때 여학생은 서로 이웃하는 경우의 수를 구하시오.

풀이 사람은 모두 다르다고 생각해야 한다. 남학생은 파랑 1, 2, 3으로 여학생은 붉은 4,5,6,7로 구별하기로 하자.

남학생을 한 묶음으로 순열의 수를 구하고 묶음 안에서 자리를 바꾸는 순열의 수를 곱하면 된다.

남학생 묶음 1과 여학생 4명이 일렬로 늘어서는 순열의 수: $5!=120$

묶음 안에서 남학생 3명이 자리를 바꾸는 순열의 수: $3!=6$

정답: $5!\times 3!=720$

예제 남학생 3명과 여학생 4명이 일렬로 늘어설 때 남학생은 서로 이웃하지 않도록 하는 경우의 수를 구하시오.

풀이 여학생을 먼저 일렬로 세우고 사이에 남학생이 들어가면 된다.

여학생 4명이 일렬로 서는 순열의 수: $4!=24$

남학생이 설 수 있는 공간 ABCDE 5개 가운데 셋을 뽑는 순열의 수: ${}_5 P _3=60$ 

정답: $4! \times {}_5 P _3=24 \times 60=1440$ 

경우의 수를 세는 문제는 단순해 보이지만 생각만큼 마냥 쉽지는 않다. 문제에 따라 순열이나 조합의 수를 적절하게 활용하는 능력을 길러야 한다.

모든 문제를 꿰뚫는 방법은 없다. '순서를 없앨 때는 나누고 만들 때는 곱한다.'를 기억하면 좋을 것이다.