2016년 10월 가형 30번

30. $1$부터 $9$까지의 자연수가 하나씩 적혀 있는 $9$개의 공이 주머니에 들어 있다. 이 주머니에서 공을 한 개씩 모두 꺼낼 때, $i$번째($i=1,~2,~\cdots,~9$) 꺼낸 공에 적혀 있는 수를 $a_i$라 하자. $1<p<q<9$인 두 자연수 $p,~q$에 대하여 $a_i$가 다음 조건을 만족시킨다.

(가) $1\le i<p$이면 $a_i<a_{i+1}$이다.

(나) $p\le i<q$이면 $a_i>a_{i+1}$이다.

(다) $q\le i<9$이면 $a_i<a_{i+1}$이다.

$a_1=2,~a_p=8$인 모든 경우의 수를 구하시오. (단, 꺼낸 공은 다시 넣지 않는다.)

---

i. 정리

뭐 딱히 다시 쓸 필요없을 거 같고..

ii. 생각

• 이해를 돕기 위해 수형도를 대충 그려보자.

  

  오호라 수형도를 대충 그리고 보니

  $a_q=1,~a_9=9$임을 알 수 있다!

• 채워나가야 할 $a_n=3,~4,~5,~6,~7$

• 이제 경우를 나누어야 할 차례인가보다....

  1. $p=2\quad \longrightarrow\quad\begin{matrix} q=3&1 \\ q=4 &{}_5C_1&a_3\text{에 들어갈 수}\\ q=5&{}_5C_2&a_3,~a_4\\ q=6&{}_5C_3&a_3,~a_4,~a_5\\ q=7&{}_5C_4&a_3,~a_4,~a_5,~a_6\\ q=8&{}_5C_5&a_3,~a_4,~\cdots ,~a_7 \end{matrix}$

   

  1. $p=3\quad \longrightarrow\quad \begin{matrix}q=4&{}_5C_1\times _4C_0&a_2\text{와 나머지}\\ q=5&{}_5C_1\times _4C_1 &a_2\text{와} a_4\\ q=6&{}_5C_1\times _4C_2\\ q=7&{}_5C_1\times _4C_3\\ q=8 &{}_5C_1\times _4C_4 \end{matrix}$

   

  1. $p=4\quad \longrightarrow\quad \begin{matrix}q=5 \\ q=6\\ q=7 \\ q=8\end{matrix}$

  규칙을 생각하자.

• $p=2$일 때,

  $\sum\limits_{r=0}^5 {}_5C_r =2^5$

• $p=3$일 때,

  $\sum\limits_{r=0}^4 {}_5C_1\times_4C_r=5\times2^4$

• $p=4$일 때,

  $\sum\limits_{r=0}^3 {}_5C_2\times _3C_r=_5C_2\times 2^3$

• $p=5$일 때,

  $\sum\limits_{r=0}^2 {}_5C_3\times _2C_r=_5C_3\times 2^2$

• $p=6$일 때,

  ${}_5C_4\times 2$

• $p=7$일 때,

  ${}_5C_5$

$\therefore~32+80+80+40+10+1=243$