카탈란수

카탈란수의 활용

이전 글 이전 글에서 카탈란 수는 적당한 대응을 통해 많은 문제를 푸는 데 사용할 수 있다고 하였다. 그 문제들의 목록은 다음과 같다. 경로의 수 문제 다각형 나누기 문제 이진트리 문제 괄호 열고 닫기 문제 입출력 문제 한 요소가 다른 요소보다 항상 크게 유지하는 문제 이 글에서는 각 문제를 카탈란 수에 대응시키는 방법에 대해 알아보겠다. 1. 경로의 수 문제 이 문제는 이전 글에서 다루었으니 넘어가겠다. 설명 2. 한 요소가 다른 요소보다 항상 크게 유지하는 문제 같은 개수의 X와 Y를 활용해 만드는 단어 중 단어의 처음에서 X와 Y의 개수를 셌을 때 항상 X의 개수가 Y의 개수 이상인 단어의 개수를 구하여라. 이 문제는 경로의 수 문제로 대응하여 카탈란 수로 대응할 수 있다. 길이가 $2n$인 단어를..

카탈란 수의 점화식

다음 글 이 글의 마지막 부분에서 카탈란 수는 (0, 0)에서 (n, n)까지 $y=x$ 그래프보다 위에 있는 점을 통과하지 않고, 격자점만을 지나며 이동하는 경우의 수라고 하였다. 카탈란 수는 다음 일반항으로 정의되는 수열이다. $C_n=\frac{1}{n+1}{}_{2n}\mathrm{C}_n$ 이 일반항이 어떻게 유도되었는지는 이전 글을 찾아보기 바란다. 이번에는 이 수열의 성질을 응용하는데 초점을 맞출 것이다. 카탈란 수는 다음 점화식을 가지고 있다. $C_{n+1}$$=\displaystyle\sum_{i+j=n}C_i C_j$$=C_0C_n+C_1C_{n-1}$$+\cdots $$+C_{n-1}C_1+C_nC_0$ 이는 카탈란 수가 경로의 수 문제와 대응됨을 생각하면 어렵지 않게 설명할 수 있..

경우의 수 - 경로의 수 Pt. 2

알림: 이 글은 경로의 개수 Pt. 1의 심화 내용입니다. 앞선 글을 이해하지 못한 상태로 이 글을 읽으시면 많이 어려우실 수 있습니다. 우리는 앞서 격자모양의 지도에서 최단거리를 구하는 방법을 탐구하였다. 이번에서도 특별한 경우에서 최단경로를 구해보자. 들어가기 먼저 이번 글에서 내내 다루게 될 한 개의 문제를 소개하겠다. 문제: 왼쪽과 같은 지도가 있다. A에서 B까지의 최단경로 중 푸른색 선분 위의 점을 통과하지 않는 경로의 개수를 구하여라 A점을 제외한 붉은색 선분 위의 점을 통과하지 않는 경로의 개수를 구하여라. 이번 글에서는 위의 문제만 다룰 것이다. 문제의 조건과 상황을 잘 이해하자. 예를 들면 1번의 경우 Fig1-1a와 같은 경로는 되는 경로이며 Fig1-1b와 같은 경로는 되지 않는 경..