[문제 풀이] 경우의 수, 중복 조합의 응용

다음 조건을 만족하는 자연수 $a_1,a_2,a_3,a_4,a_5,a_6$의 모든 순서쌍 $\p{a_1,a_2,a_3,a_4,a_5,a_6}$의 개수를 구하시오.

(가) $1\le a_1<a_2\le a_3<a_4\le a_5<a_6\le10$
(나) $\sum_{n=1}^6(-1)^na_n=5$

---

(나)의 항들을 순서대로 둘씩 묶어서 생각하면 $\p{a_2-a_1}+\p{a_4-a_3}+\p{a_6-a_5}=5$가 되죠. (가)의 부등호에 따라 $k=1,2,3$에 대해 $a_{2k}-a_{2k-1}>0$이고, 이들의 합이 5라는 사실로부터, 둘은 1이고 남은 하나는 3이거나 하나는 1이고 나머지는 2여야 해요. 순서에 따라 총 6가지의 경우가 생기죠.

$a_n$이 순서에 따라 크기가 커진다는 사실을 이용해, $m=1,2,3,4,5$에 대해 $d_{m+1}=a_{m+1}-a_m$로 바꿔주면 $a_1+d_2+d_3+d_4+d_5+d_6=a_6\le10$이 성립한다는 걸 알 수 있어요. $d_1=a_1-1$이라 하고 $d_2+d_4+d_6=5$라는 사실을 이용하면 $d_1+d_3+d_5+6\le10$이라고 정리할 수 있죠. $d_0=4-d_1-d_3-d_5$라 하면 $d_0,d_1,d_3,d_5$는 모두 음이 아닌 정수로 그 합이 4라는 걸 알 수 있어요.

위의 설명이 바로 중복 조합이죠. 네 개의 음이 아닌 정수의 합이 4이니 여기서 가능한 경우의 수는\[\mc44=\binom{4+4-1}4=35\]죠. 여기서 $\binom ab$는 $a$개 중에서 $b$개를 선택하는 조합, $\mc ab$는 중복 조합을 표현한 거예요.

위의 각 경우에 대해 $d_2,d_4,d_6$의 경우는 처음에 설명한 것처럼 6가지이니 구하고자 하는 순서쌍의 개수는 이 두 경우의 수를 곱한 210이라는 걸 알 수 있죠.