[옥동수학학원][더플러스수학] 카탈란 수 (1)

이산수학 최경식(경문사)에서의 예에서 시작해보자.
요금이 $\displaystyle 5,000$원인 어떤 영화가 보고싶어 $\displaystyle 6$명이 극장에 들어가려고 한다. 그 중 $\displaystyle 3$명은 $\displaystyle 5,000$원짜리를 가지고 있고 나머지 $\displaystyle 3$명은 $\displaystyle 10,000$원짜리를 가지고 있다. 매표소에는 잔돈이 준비되어 있지 않다. 모두 입장할 수 있도록 일렬로 서는 방법의 수를 구한다. 단, 사람들은 구별하지 않는다. 즉, 같은 돈을 가진 사람이면 누가 앞에 서든지 문제삼지 않는다.
풀이) 사람들을 구별하지 않으므로 $\displaystyle 5,000$짜리를 가진 사람을 $\displaystyle A$, $\displaystyle 10,000$짜리를 가진 사람을 $\displaystyle B$라 하면 매표소에 잔돈이 없으므로 $\displaystyle B$가 맨 앞에 올 수는 없다. 또, 어느 $\displaystyle A$에 대해서도 그 앞에 있는 $\displaystyle A$의 개수보다 $\displaystyle B$의 개수가 더 많아서는 안된다. 즉 예를 들어

$\displaystyle ABBAAB$

인 경우는 모두 극장에 들어 갈 수 없다. 이러한 상황을 고려하여 입장할 수 있게 줄 설 수 있는 경우를 구해보면

$\displaystyle AAABBB,~AABABB,~AABBAB,~ABAABB,~ABABAB$

로 모두 $\displaystyle 5$가지이다.
이 상황을 좌표평면에 나타내어 최단거리의 문제로 바꿔 보자.
$\displaystyle A$를 $\displaystyle \rightarrow$, $\displaystyle B$를 $\displaystyle \uparrow$로 나타내고 출발점을 $\displaystyle \mathrm{O}(0,~0)$으로 하면 원점  $\displaystyle \mathrm{O}$에서 $\displaystyle (3,~3)$으로 가는 최단거리 중에서 $\displaystyle y \leq x$ 만족하면서 $\displaystyle (3,~3)$에 도달하는 최단경로의 수와 같다. 
그림으로 나타내면 아래와 같다.

위의 그림에서 보듯이 파란색의 길을 따라 원점 $\displaystyle \mathrm{O}$에서 $\displaystyle (3,~3)$에 이르는 최단 경로의 수 $\displaystyle 5$와 같다.
초등학교 때 배운 방법으로 개수를 세면 아래의 그림과 같다.

* 이 수를 카탈란 수라고 하고 기호로 $\displaystyle C_3$라고 한다.
또, 세 쌍의 열린괄호(open parenthesis $\displaystyle '('$)와 닫힌 괄호 (closed parenthesis $\displaystyle ')'$)를 써서 만들 수 있는 올바른 괄호의 수도 역시 카탈란 수 $\displaystyle C_3$이다. 

$\displaystyle ((())),~(()()),~(())(),~()(()),~()()()$

예를 들어 $\displaystyle (()())$를 위의 그림에서 어떤 경로로 원점에서 $\displaystyle (3,~3)$에 도달하는 것인지 알아 보자.
열린괄호('(')를 $\displaystyle \rightarrow$로 닫힌 괄호(')')를 $\displaystyle \uparrow$로 표시하면 $\displaystyle \textcolor{red}{(~(~)~(~)~)}$은 $\displaystyle \textcolor{red}{\rightarrow~ \rightarrow ~\uparrow ~\rightarrow~\uparrow~\uparrow}$이므로 그림으로 나타내면 아래와 같다.

또, $\displaystyle 3$개의 $\displaystyle \nearrow$와 $\displaystyle 3$개의 $\displaystyle \searrow$를 이용하여 평지에 산을 그리는 방법의 수도 역시 카탈란 수 $\displaystyle C_3 =5$개이다. 그림으로 나타내면 아래와 같다.

위의 그림 중에서

의 그림을 원점 $\displaystyle (0,~0)$에서  $\displaystyle (3,~3)$에 이르는 경로로 나타내어 보자.
$\displaystyle \nearrow$를 $\displaystyle \textcolor {red}{\rightarrow}$로 $\displaystyle \searrow$를 $\displaystyle \textcolor {red}{\uparrow}$로 나타내면

$\displaystyle  {\rightarrow~\rightarrow~\uparrow~\uparrow~\rightarrow~\uparrow}$

이다. 따라서 그 경로는 아래 그림과 같다.

다음 편에서는 카탈란 수 $\displaystyle C_n$의 일반항이 $$\displaystyle C_n ={}_{2n} \mathrm{C}_{n}-{}_{2n}\mathrm{C}_{n-1}= \frac{1}{n+1} {}_{2n}\mathrm{C}_{n}$$ 이고 점화식이 $$\displaystyle C_0 =1,~C_n = C_0 C_{n-1}+C_1 C_{n-2} +\cdots+C_i C_{(n-1)-i}+\cdots+C_{n-1} C_0$$ 임을 보이겠다.

더플러스수학학원
울산 남구 대공원입구로21번길 45-1 2층
https://naver.me/xIhg4CMX

더플러스수학학원 : 네이버

과고1학년, 2학년 대신대비를 위해 더플러스수학학원의 구술시스템에서 실제로 하고 있는 문제를 보시려거나 과학고 3학년 AP미적분학을 준비하고자 하거나 대학교1학년 미적분학에 대해 공부하려고 하면 더플러스수학 프리미엄콘텐츠 를 이용해 보세요.
https://naver.me/FsR64KUy

과학고전문더플러스수학 : 네이버 프리미엄콘텐츠

2021.08.03 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 - 일반항(2)

[더플러스수학] 카탈란 수 - 일반항(2)

2021.08.03 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 - 점화식(3)

[더플러스수학] 카탈란 수 - 점화식(3)

2021.08.06 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 - 생성함수(4)

[더플러스수학] 카탈란 수 - 생성함수(4)