자연계열 3번

(1) 숫자 2가 두 번 나오는 네 자리 자연수들을 크기 순서로 늘어놓으면

$\displaystyle 1122,\ 1212,\ 1221,\ 2112,\ 2121,\ 2211$

이므로, $\displaystyle r(1221)=3$이다.

숫자 2만 세 번 나오는 경우, 한 가지 수 $\displaystyle 222$만 나오므로 $\displaystyle r(222)=1$이다.

(2) $\displaystyle k=0$인 경우, 즉 $\displaystyle A$의 원소가 숫자 1로만 이루어진 경우, $\displaystyle A$는 하나의 원소만 가지고, $\displaystyle A=A_1,A_2=\varnothing$이다. 이때, $\displaystyle A_1$과 $\displaystyle A_2$의 원소의 개수는 각각 1, 0이다. 또한, $\displaystyle n=k$인 경우, 즉 $\displaystyle A$의 원소가 숫자 2로만 이루어진 경우, 비슷하게, $\displaystyle A_1=\varnothing$이고, $\displaystyle A_1$과 $\displaystyle A_2$의 원소의 개수는 각각 0, 1이다.

위의 두 경우를 제외한 경우, 즉 $\displaystyle 0<k<n$인 경우, 집합 $\displaystyle A_1$은 숫자 2의 개수가 $\displaystyle k$인 $\displaystyle (n-1)$자리 자연수들의 집합이므로 $\displaystyle {}_{n-1}\mathrm C_k$개의 원소를 가진다. 또한, 이 경우, 집합 $\displaystyle A_2$는 숫자 2의 개수가 $\displaystyle k-1$인 $\displaystyle (n-1)$자리 자연수들의 집합이므로 $\displaystyle {}_{n-1}\mathrm C_{k-1}$개의 원소를 가진다.

(3) 숫자 2가 세 번 나오는 일곱 자리 자연수들의 집합을 $\displaystyle B$라 하면, $\displaystyle 2112211\in B$이다. 이 수에 숫자 1을 앞에 붙인 여덟 자리 자연수 $\displaystyle 12112211$의 순위를 다음과 같이 계산한다.

숫자 2가 세 번 나오는 여덟 자리 자연수들의 집합을 $\displaystyle A$, 그중 1로 시작하는 수의 집합이 $\displaystyle A_1$이라 하면, $\displaystyle 12112211\in A_1\subset A$이다. $\displaystyle B$의 각 원소의 앞에 숫자 1을 붙이면 $\displaystyle A_1$의 원소가 되고, 거꾸로 $\displaystyle A_1$의 원소의 앞의 숫자 1을 떼면 $\displaystyle B$의 원소가 되므로, 이 대응은 $\displaystyle A_1$과 $\displaystyle B$사이의 일대일 대응이고, 순서를 보존한다. 제시문 (나)의 (a)와 (b)에 의해 $\displaystyle A_1$의 원소들은 순위가 1부터 시작하므로, 이 대응관계는 순위를 보존한다. 즉,

$\displaystyle r(12112211)=r(2112211)=26$

이다.

(4) 숫자 2가 두 번 나오는 일곱 자리 자연수들의 집합을 $\displaystyle B$라 하면, $\displaystyle 1122111\in B$이다. 이 수에 숫자 2를 앞에 붙인 여덟 자리 자연수 $\displaystyle 21122111$의 순위를 다음과 같이 계산한다.

숫자 2가 세 번 나오는 여덟 자리 자연수들의 집합을 $\displaystyle A$, 그중 숫자 2로 시작하는 원소들의 집합을 $\displaystyle A_2$라 하면, $\displaystyle 21122111\in A_2\subset A$이다. $\displaystyle B$의 원소의 앞에 숫자 2를 붙이면 $\displaystyle A_2$의 원소가 되고, 거꾸로 $\displaystyle A_2$의 원소의 앞의 숫자 2를 떼면 $\displaystyle B$의 원소가 되므로, 이 대응은 $\displaystyle A_2$과 $\displaystyle B$사이의 일대일 대응이고, 순서를 보존한다. 제시문 (나)의 (a)와 (b)에 의해 $\displaystyle A_2$의 원소들은 순위가 $\displaystyle A_1$의 원소의 개수$\displaystyle +1={}_{7}\mathrm C_3+1=35+1$부터 시작하므로, $\displaystyle A_2$의 원소의 순위는 이 대응에 의한 $\displaystyle B$의 원소의 순위에 $\displaystyle {}_{7}\mathrm C_3$를 더한 값이다. 즉,

$\displaystyle r(21122111)={}_{7}\mathrm C_3+r(1122111)=35+10=45$

이다.

(5) 위 (3)과 같은 식으로 논증하면, 숫자 1과 2로 이루어진 자연수 $\displaystyle x$와 $\displaystyle y$에 대하여,

(i) $\displaystyle x$가 $\displaystyle y$의 앞에 숫자 1을 붙인 수인 경우,

$\displaystyle r(x)=r(y)$

이다.

또한, 위 (4)과 같은 식으로 논증하여,

(ii) $\displaystyle x$가 $\displaystyle y$의 앞에 숫자 2를 붙인 수인 경우,

$\displaystyle y$의 자릿수 $\displaystyle m$과 $\displaystyle y$에 숫자 2가 나오는 횟수 $\displaystyle k$에 대하여,

$\displaystyle r(x)={}_{m}\mathrm C_{k+1}+r(y)$

이다.

이 두 가지를 반복적으로 적용하면,

$\displaystyle \begin{aligned}r(1221121112)&=r(221121112)\\&={}_{8}\mathrm C_4+r(21121112)\\&=\cdots\\&={}_{8}\mathrm C_4+{}_{7}\mathrm C_3+{}_{4}\mathrm C_2+r(1112)\\&=70+35+6+1=112\end{aligned}$

이다.