-
[더플러스수학] 카탈란 수 - 일반항(2)수학과 공부이야기 2021. 8. 3. 16:46
2021.08.02 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 (1)
[더플러스수학] 카탈란 수 (1)
이산수학 최경식(경문사)에서의 예에서 시작해보자. 요금이 \displaystyle 5,000원인 어떤 영화가 보고싶어 \displaystyle 6명이 극장에 들어가려고 한다. 그 중 \displaystyle 3명은 \(\displaystyle..
plusthemath.tistory.com
앞 편의 글에서 카탈란 수 \displaystyle C_n 가 무엇인지 또, 실생활에서는 어떻게 활용되는지에 대해 알아 보았다.
이 편에서는 카탈란 수 \displaystyle C_n 의 일반항이 어떤 과정을 거쳐서\displaystyle C_n = \frac{1}{n+1} {}_{2n} \mathrm{C}_{n}= {}_{2n}\mathrm{C}_{n}-{}_{2n}\mathrm{C}_{n-1}
이 되는지 알아보자.
앞 편의 글 에서의 예인 \displaystyle 5,000원을 가진 사람을 \displaystyle A , \displaystyle 10,000원을 가진 사람을 \displaystyle B 라 하자. 입장을 할 수 있는 경우는 어떤 \displaystyle A 에 대해서도 이 \displaystyle A 앞에서는 \displaystyle A 의 개수보다 \displaystyle B 의 개수가 더 많아서는 안된다.
여기서 우리는 여사건을 이용하여 계산하자. \displaystyle A \displaystyle 3 개, \displaystyle B \displaystyle 3 개를 나열하는 총 경우의 수\displaystyle \frac{6!}{3!3!} ={}_6 \mathrm{C}_3
에서 입장하지 못하는 경우의 수를 빼서 계산하겠다. 이 경우를 분류해보자.
먼저 제일 앞에 \displaystyle B 가 오면 입장할 수 없다. 즉\displaystyle \textcolor {red}{B} \times \times \times \times \times
이 때, \displaystyle \times \times \times \times \times 에는 \displaystyle A 가 \displaystyle 3 개, \displaystyle B 가 \displaystyle 2 개 있으므로 나열하면
\displaystyle \frac{5!}{3! \times 2!}={}_5 \mathrm{C}_3 =10
하나의 예로 \displaystyle \textcolor {red}{B} \textcolor {blue}{AAABB} 이 있다.
또, \displaystyle AB \textcolor {red}{B} \times \times \times 일 때도 입장할 수 없다. 이 경우에 \displaystyle \times \times \times \times 에는 \displaystyle A 가 \displaystyle 2 개, \displaystyle B 가 \displaystyle 1 개 있으므로 나열하면\displaystyle \frac{3!}{2! \times 1!}={}_3 \mathrm{C}_2 =3
하나의 예로 \displaystyle AB\textcolor {red}{B} \textcolor {blue}{AAB} 이 있다.
또, \displaystyle ABAB \textcolor {red}{B} \times 일 때도 입장할 수 없다. 이 경우에 \displaystyle \times 에는 \displaystyle A 가 \displaystyle 1 개, \displaystyle B 가 \displaystyle 0 개 있으므로 나열하면\displaystyle \frac{1!}{1! \times 0!}={}_1 \mathrm{C}_1 =1
하나의 예로 \displaystyle ABAB\textcolor {red}{B} \textcolor {blue}{A} 이 있다.
또, \displaystyle AABB \textcolor {red}{B} \times 일 때도 입장할 수 없다. 이 경우에 \displaystyle \times 에는 \displaystyle A 가 \displaystyle 1 개, \displaystyle B 가 \displaystyle 0 개 있으므로 나열하면\displaystyle \frac{1!}{1! \times 0!}={}_1 \mathrm{C}_1 =1
하나의 예로 \displaystyle AABB\textcolor {red}{B} \textcolor {blue}{A} 이 있다.
따라서 구하는 경우의 수는\displaystyle \frac{6!}{3!3!} ={}_6 \mathrm{C}_3 -15 =5개
이다.
여기서 입장할 수 없는 경우를 다시 관찰해보자. 위에서 구체적인 예로 든 경우에서 맨앞의 문자에서 빨간색 \displaystyle \textcolor {red}{B} 까지의 문자를 \displaystyle A 를 \displaystyle B , \displaystyle B \displaystyle A 로 바꿔서 아래처럼 정리해보자.\displaystyle \textcolor {red}{B} \textcolor {blue}{AAABB} ~~\Longleftrightarrow ~~\textcolor {red}{A} \textcolor {blue}{AAABB}
\displaystyle AB\textcolor {red}{B} \textcolor {blue}{AAB} ~~\Longleftrightarrow ~~\textcolor {red}{BAA} \textcolor {blue}{AAB}
\displaystyle ABAB\textcolor {red}{B} \textcolor {blue}{A} ~~\Longleftrightarrow ~~\textcolor {red}{BABAA} \textcolor {blue}{A}
\displaystyle AABB\textcolor {red}{B} \textcolor {blue}{A} ~~\Longleftrightarrow ~~\textcolor {red}{BBAAA} \textcolor {blue}{A}위의 오른쪽의 배열에서 빨간색은 고정되어 있고, 푸른색은 배열할 수 있으므로 이 총 경우의 수는 \displaystyle AAAABB를 배열한 경우의 수인 \displaystyle {}_6 \mathrm {C}_2 또는 \displaystyle {}_6 \mathrm {C}_4 개다.
따라서 \displaystyle C_4={}_6 \mathrm {C}_3 - {}_6 \mathrm {C}_2 =5개다.
위의 과정에서 붉은 색 \displaystyle \textcolor {red}{B} 앞의 \displaystyle A와 \displaystyle B를 바꾼다는 것은 아래의 과정에서는 직선 \displaystyle {y=x+1}에 대칭이동한다는 것임을 염두에 두자.
위의 과정을 좀 더 다르게 접근하자.
\displaystyle A를 '\displaystyle \rightarrow '로, 즉 '오른쪽으로 한 칸' 옮기는 행위로, \displaystyle B를 '\displaystyle \uparrow '로, 즉 '위쪽으로 한 칸' 옮기는 행위로 바꾸면 \displaystyle A의 개수가 \displaystyle B개수보다 많야야 한다는 것은 직선 \displaystyle y=x의 위쪽으로 갈 수 없다는 것을 의미한다.
따라서 \displaystyle C_3 는 원점 \displaystyle \mathrm{O}(0,0)에서 직선 \displaystyle y=x의 위쪽으로 가지 않으면서 점 \displaystyle \mathrm{A}(3,3)으로 가는 최단 경로의 수를 의미한다.
그림으로 나타내면 아래와 같다.또, 위에서 본
\displaystyle \textcolor {red}{B} \textcolor {blue}{AAABB} ~~\Longleftrightarrow ~~\textcolor {red}{A} \textcolor {blue}{AAABB}
\displaystyle AB\textcolor {red}{B} \textcolor {blue}{AAB} ~~\Longleftrightarrow ~~\textcolor {red}{BAA} \textcolor {blue}{AAB}
\displaystyle ABAB\textcolor {red}{B} \textcolor {blue}{A} ~~\Longleftrightarrow ~~\textcolor {red}{BABAA} \textcolor {blue}{A}
\displaystyle AABB\textcolor {red}{B} \textcolor {blue}{A} ~~\Longleftrightarrow ~~\textcolor {red}{BBAAA} \textcolor {blue}{A}을 그림으로 차래대로 그리면 아래와 같다.
위의 그림에서 보듯이 원점 \displaystyle \mathrm {O}(0,0)에서 \displaystyle (3,3) 까지로 가는 경로 중 카탈란 수 \displaystyle C_3 를 만족하지 않는 경로는 반드시 직선 \displaystyle y=x+1와 최초로 만나는 점 \displaystyle \mathrm {P}이 반드시 존재한다. 그리고 원점 \displaystyle \mathrm {O}(0,0)에서 점 \displaystyle \mathrm {P}까지 가는 경로를 직선 \displaystyle y=x+1에 대하여 대칭이동하면 점 \displaystyle \mathrm {O}'(-1, 1)에서 점 \displaystyle \mathrm {P}까지 가는 경로가 되고 또, 점 \displaystyle \mathrm {P}에서 \displaystyle (3,3)까지 가는 경로를 연결하면 결국 \displaystyle \mathrm {O}'(-1, 1)에서 \displaystyle (3,3)까지 가는 경로가 \displaystyle \mathrm O (0,0)에서 \displaystyle (3,3)까지의 경로 중 카탈란 수를 만족하는 않는 경로를 나타낸다. 위의 그림에서는 오른쪽 그림이다.
위의 과정을 일반화하여 카탈란 수의 일반항을 구해보자.
카탈란 수 \displaystyle C_n은 원점 \displaystyle \mathrm O (0,~0)에서 \displaystyle (n,~n)까지 직선 \displaystyle y =x를 넘지 않으면서 가는 최단 경로의 수이다.따라서 직선 \displaystyle y =x를 넘으면서 \displaystyle (n,~n)까지 가는 경로의 수는 원점을 직선 \displaystyle y=x+1에 대하여 대칭이동한 점인 \displaystyle (-1,~1)에서 \displaystyle (n,~n)까지 가는 경로의 수이다. 즉
\displaystyle {}_{2n} \mathrm {C} _{n-1}= \frac{2n!}{(n-1)! \times (n+1)!}
이다.
따라서 카탈란 수 \displaystyle C_n 은
\displaystyle \begin{align} C_n &= {}_{2n} \mathrm{C}_n -{}_{2n} \mathrm{C}_{n-1} \\& =\frac{1}{n+1} {}_{2n} \mathrm{C}_n \end{align}
2021.08.03 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 - 점화식(3)
[더플러스수학] 카탈란 수 - 점화식(3)
카탈란 수란 무엇인가?에 대한 글 2021.08.02 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 (1) 카탈란 수의 일반항에 대한 설명글 2021.08.03 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 -
plusthemath.tistory.com
2021.08.06 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 - 생성함수(4)
[더플러스수학] 카탈란 수 - 생성함수(4)
2021.08.03 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 - 점화식(3) [더플러스수학] 카탈란 수 - 점화식(3) 카탈란 수란 무엇인가?에 대한 글 2021.08.02 - [수학과 공부이야기] - [더플러스수학] 카
plusthemath.tistory.com
과고1학년, 2학년 대신대비를 위해 더플러스수학학원의 구술시스템에서 실제로 하고 있는 문제를 보시려거나 과학고 3학년 AP미적분학을 준비하고자 하거나 대학교1학년 미적분학에 대해 공부하려고 하면 더플러스수학 프리미엄콘텐츠 를 이용해 보세요.
https://naver.me/FsR64KUy과학고전문더플러스수학 : 네이버 프리미엄콘텐츠
더플러스수학학원은 울산 옥동에 위치한 수학 전문 학원으로, 과학고 학생들의 내신 대비에 특화된 맞춤형 학습을 제공합니다. 권도형 원장은 서울대 무기재료공학과 졸업, 부산대 수학과 석사
contents.premium.naver.com
'수학과 공부이야기' 카테고리의 다른 글
[더플러스수학] 카탈란 수 - 생성함수(4) (0) 2021.08.06 [더플러스수학] 카탈란 수 - 점화식(3) (1) 2021.08.03 2020학년도 서울 일반전형 면접 및 구술고사[수학]-자연,공대 (0) 2021.08.02 [옥동수학학원][더플러스수학] 카탈란 수 (1) (0) 2021.08.02 [전자책] 수리논술 심층면접대비 미적분 제1부 [더플러스수학] (0) 2021.06.30