[신정수학학원][옥동수학학원]##[더플러스수학] 카탈란 수 (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

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

더플러스수학학원 신정지점
울산 남구 문수로423번길 8 309호
https://naver.me/FTOL1Hgt

더플러스수학학원 신정지점 : 네이버

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

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

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

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

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

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