번외: 카탈란 수를 선형대수로 풀 수 있다고?

📘 카탈란 수열 시리즈

• 🌱 카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?
• 🔢 카탈란 수열의 일반항 구하기: 조합으로 구하기
• 🧮 카탈란 수열의 점화식 구하기
• 📐 카탈란수의 응용: n+2각형에서 삼각형으로 분할하기
• 🧪 카탈란 수열의 일반항을 생성함수로 구해보자 (1)
• 🧰 이항정리를 이항급수로 확장하기
• 🔍 카탈란 수열의 일반항을 생성함수로 구해보자 (2)
• 🔄 라그랑주 역함수 정리 (Lagrange Inversion Theorem)
• 🧠 번외: 카탈란 수를 선형대수로 풀 수 있다고?

0. 서론

사실상 카탈란 수 시리즈는 저번 포스팅으로 공식적으로 마무리.. 지만, 또 재밌는 주제를 발견해서 '번외'로 한번 써볼까 합니다.
제목에서 아실 수 있다시피 오늘의 주제는 선형대수인데요.
선형대수는 '선형성(linearity)'이 유지되는 문제를 다루는 수학 분야입니다.
따라서 '선형'문제였던 피보나치 수열의 일반항을 구하는 문제는 선형대수로 아주 멋있게 풀 수 있었죠.
그러나 카탈란 수열의 경우 이 점화식 자체가 비선형이기때문에 특성방정식도 사용할 수 없고, 선형대수로도 풀 수 없습니다.
근데, 왜 제목은 선형대수로 풀 수 있다고 해 놓았을까요?
바로 이 카탈란 수열 문제를 직접 해부하는 것이 아니라, Dyck path문제로 바꾸어 전이행렬(Transition matrix)을 놓고 이를 통해서 풀 수 있기 때문입니다. 재밌지 않나요?
그럼 바로 이 재밌는, 게임과 같은 문제를 풀어보도록 하겠습니다.
 
참, 이전까지 저희는 항상 Dyck path를 n x n 격자위에서 움직이는 경로로 생각해서 풀었었는데요, 이제는 진짜로 수직선 위에서 ↗오른쪽 위로 올라가는 경우와 ↘오른쪽 아래로 내려가는 경우를 가지고 생각해보겠습니다.
 

사실 수직선을 대각선으로 보든, 수평선 위의 우상향·우하향으로 보든 결국 동일한 Dyck path를 다르게 해석한 것일 뿐입니다. 결국 시점에서 종점까지 이 선을 넘어가지 않고 움직이는 경우의 수 인거죠.
이렇게 수평선으로 놓고 보면 Dyck path는 수평선 아래로 내려가지 않는 경우를 말하겠군요.
 
 

1. Dyck path로 전이행렬을 만들자

1-1. Dyck path를 다시 한번 살펴보자

Dyck path는 이제 너무나도 익숙하시겠지만, 다시한번 간단하게 정리하면

Dyck path란 총 2n개의 스텝으로 구성된 경로로, 각 스텝은 U (up: ↗(+1)) 또는 D (down: ↘(-1))로 구성됩니다. 이때 항상 $ U \ge D $, 즉 현재 높이 h ( = #U - #D )가 음수가 되지 않아야 한다는 조건을 만족해야 합니다.
(여기서 #은 Number of 라는 뜻으로, 각각 U의 갯수와 D의 갯수를 뜻합니다.)

그리고 한가지 더, 실제 Dyck path를 보면 점 자체의 이동이 x축으로도 일어나지만 여기서는 y축의 높이 만을 중심으로 보겠습니다.

1-2. Dyck path를 상태 전이 모델로 모델링해보자

이를 상태 $ h \in \mathbb{Z}_{\ge 0} $(기호가 어렵지만 결국 그냥 "높이 h가 0이상의 정수 영역에 있다"라는 의미입니다.)로 보는 순간, 우리는 Dyck path를 다음과 같이 모델링 할 수 있습니다.
 

• 상태 h: 현재 높이 = #U - #D
• 입력 기호: U 또는 D
• 시작 상태: h = 0
• 제약조건: $ h \ge 0 = i \ge j$
• 종료조건: 길이 2n이며, 최종 상태 h = 0

 
 
그리고 이 모델을 통해 다음과 같은 상태 전이 구조가 생깁니다:

• U를 선택하면: 높이 $h \to h + 1$
• D를 선택하면: 높이 $h \to h - 1$ (단, $h > 0$일 때(=$ i \ge j $)만 허용)

이렇게 정의된 상태 전이 구조는 바로 전이행렬(Transition matrix)로 표현할 수 있습니다.
 
 

1-3. 전이행렬을 정의하자

이제 상태 공간을 전이행렬 $ \mathbb{A} $로 나타내보겠습니다.
 
상태 공간은 높이 h=0, 1, ..., n 까지 존재하며, 이때 전이행렬 $ \mathbb{A} $는 다음과 같이 정의할 수 있습니다.
요소별 index $ i, \ j $를 현재 높이 i에서 j로 가는 $ h = i \to j $라고 본다면,
$ \mathbb{A}_{i,j} = \begin{cases} 1 & \mathrm{if} \ j=i+1 & \mathrm{(U \ 이동)} \\ 1 & \mathrm{if} \  j=i-1 & \mathrm{(D \ 이동 \ and \ }i>0) \\ 0 & \mathrm{otherwise} \end{cases} $
이렇게 정의되겠죠.
 
예를 들어, n = 2일 때 상태공간은 h = 0, 1, 2 즉, 3x3 행렬이고, 다음과 같은 형태가 됩니다.
$ \mathbb{A} = \begin{bmatrix} \textcolor{red}{0}&\textcolor{green}{1}&0 \\ \textcolor{blue}{1}&\textcolor{red}{0}&\textcolor{green}{1} \\ 0&\textcolor{blue}{1}&\textcolor{red}{0} \end{bmatrix} $
살펴보면, 각자 자기자신으로는 움직이지 못합니다. 즉, (0,0), (1,1), (2,2)는 모두 0입니다.
한 단계 상승(0->1, 1->2)은 가능합니다. 즉, (0,1), (1,2)는 1입니다.
한 단계 하강(1->0, 2->1)은 가능합니다. 단, i가 j보다 커야합니다. 즉, (1,2), (2,1)은 1입니다.
한 번에 두 칸 이동은 불가능 합니다. 즉, (0,2), (2,0)는 0입니다.
 
이렇게 움직임이 가능한 부분을 매핑하여 "높이 상태 전이"를 표현하는 전이행렬 $ \mathbb{A} $를 정의했습니다.
 
 

2. 2n번 이동하니까 전이행렬을 2n번 제곱하자

Dyck path는 총 2n개의 이동으로 구성됩니다. 전이행렬 $ \mathbb{A} $가 한 번의 상태 전이를 나타낸다면, 총 경로의 상태 전이는:

$ \mathbb{A}^{2n} $

즉, 전이행렬을 2n번 곱한 결과가 전체 경로 공간에서 상태 간 도달 가능성을 모두 표현합니다.
 
여기서 이 전이행렬은 정확히는 '움직일 수 있는 방법'이라기보다는 '움직이고 난 후의 결과'로 보는게 타당합니다.
현재 저희는 첫번째 이동이라는 특성상 '움직일 수 있는 방법' = '움직이고 난 후의 결과'이므로 움직일 수 있는 방법을 매칭한 것과 마찬가지지만, 이를 제곱하여 실제로 n번 이동의 결과를 행렬로 표현하면 각 index의 해석을 '높이 $i \to j$'로 이동가능한 경우의 수로 보아야 옳습니다.
 
 

3. 전이행렬의 요소별 의미

전이행렬 $ \mathbb{A} $의 $(i, j)$ 원소 $ \mathbb{A}^k_{i, j}$는 다음을 의미합니다:

> "높이 i에서 출발하여 k번의 이동 후 높이 j에 도달하는 경로의 수"

특히 $ \mathbb{A}^{2n}_{0, 0} $은 "높이 0에서 시작해서 2n 스텝 후 다시 높이 0으로 돌아온 모든 경로의 수"를 의미하게 되죠.
따라서 다른 행(가령 높이 1에서 출발해서 1로 돌아오는 등)은 의미가 없고, 다른 열(가령 높이 1에서 출발해서 3에서 끝나는 등)도 의미가 없습니다. (말그대로 "전체 경로 공간에서 상태 간 도달 가능성을 모두 표현"하는게 전이함수니까요)
 
저희는 0에서 0으로 정확하게 돌아온 경우의 수만 필요하고 이것이 카탈란 수입니다.
즉, $ \mathbb{A}_{0,0} $만이 저희가 원하는 카탈란 수가 되는 것입니다.
[여기서 전이행렬 자체를 정의할 때 $ i \ge j $ 규칙을 반영하였기 때문에 음수로 내려가는 경우는 발생하지 않습니다.]
 
이것만 해도 매우 신기하죠?
근데, 문제점이.. 일단 행렬이 굉장히 크고, 그걸 2n번이나 거듭제곱 해주어야 한다는 점이 크네요...
어떻게 더 좋은수가 없을까요?
 
 

4. 한 칸만 이동하므로 대각선 근처에만 값이 있는 희소행렬 구조

위에서 전이행렬을 정의할 때를 잘 보면(즉 무조건 한번 이동한다고 하면)

1. 자기 자신으로 움직일 수는 없다
2. 한 번에 두 칸 이상 움직일 수는 없다(무조건 한 칸만 이동해야 한다)

의 두가지 조건에 의해 그렇게 움직일 수 있는 경우는 전부 0으로 막혀있었죠?
그리고 이때문에 행렬에 0이 더 많고, 오히려 움직일 수 있는 값을 나타내는 1의 갯수는 희박해 졌습니다.
이때, 우리는 이렇게 행렬 전체적으로 봤을 때 의미있는 값이 '희박' 혹은 '희소'하게 있는 행렬을 '희소행렬(sparse matrix)'라고 부릅니다.
 
그리고 움직이는 조건에서 한 번의 전이에서 높이는 +1 또는 -1만 가능하므로,

• $ \mathbb{A}_{i, i+1} = 1 $ (U)
• $ \mathbb{A}_{i, i-1} = 1$ (D)

결국, $ \mathbb{A} $는 대각선 위와 아래에만 값이 있는 띠 행렬(Band matrix) 혹은 삼중대각행렬(Tridiagonal matrix)입니다.
 
어찌되었든, 이 희소행렬이란건 딱 봐도 0이 많으니까 불필요한 연산이 많아질 수 있다는 점을 직감할 수 있습니다.
 
 

5. 상태벡터로 필요없는 연산을 줄여보자

자, 위에서 살펴봤듯이 전이행렬을 n번 제곱할때마다 n번 이동한 경우의 수를 나타내게 된다고 알게 되었습니다.
그런데 자세히보면 우리가 알고 싶은 건 0에서 0으로 돌아오는 경우의 수, 좀 더 러프하게 말하면 최소한 0에서 출발하는 경우만 세면 됩니다.
근데 전이행렬 자체를 n번 제곱하면 모든 요소에 대해서 연산이 이루어져야하니까 굉장히 비효율적입니다.(아무리 희소행렬이라도 매번 0을 곱해야 한다면 매우 비효율적이겠죠)
그래서 저희는 이제부터 '상태벡터'를 정의해보겠습니다.
 
$ \vec{v}^{(0)} = \underbrace{[1, 0, \ldots, 0]}_{[h_0, h_1, \ldots, h_n]} $
이 벡터의 지수위치에 있는 (0)이 뜻하는 것은 초기상태를 뜻하고, 이게 한번씩 상태가 전이될때마다 1씩 올려서 몇번째 상태벡터인지 표현해주겠습니다.
그리고 이 벡터가 가진 성분은 각각 $ h_0 $부터 $h_n$까지 인데, 이것이 뜻하는 건 한번의 상태 전이가 일어나고 나서 각 h위치에서 끝난 경우의 수를 나타내주는 값입니다.
그래서 한번의 전이가 일어난 상태벡터는 아래과 같이 쓰이겠죠
$ \vec{v}^{(k+1)} = \mathbb{A} \cdot \vec{v}^{(k)} $
 
여기서 n=2인 상황을 가정하면, 전이행렬 $ \mathbb{A} $는
$ \mathbb{A} = \begin{bmatrix} 0&1&0 \\ 1&0&1 \\ 0&1&0 \end{bmatrix} $
이와 같이 정의되고,
$ C_2 = \mathbb{A}^4_{(0,0)} = \begin{bmatrix} 0&1&0 \\ 1&0&1 \\ 0&1&0 \end{bmatrix}^4 $ 중 0,0요소
이렇게 정리가 되겠죠?
근데 여기서 0,0 요소를 꺼내는걸 수식으로 바꿔보자면
$ \mathbb{A}^4_{(0,0)} = \begin{bmatrix} 0&1&0 \\ 1&0&1 \\ 0&1&0 \end{bmatrix}^4 \begin{bmatrix} 1\\0\\0 \end{bmatrix} $
이렇게 될 것이고, 여기서 $ \begin{bmatrix} 1\\0\\0 \end{bmatrix} $ 이것은 $ = [1, 0, 0]^T = \vec{v}^{(0)} $이네요.
그러면 다시 써보면
$ \mathbb{A}^4_{(0,0)} = \begin{bmatrix} 0&1&0 \\ 1&0&1 \\ 0&1&0 \end{bmatrix}^4 \vec{v}^{(0)} = \vec{v}^{(4)} $
이렇게 되겠네요.
 
행렬의 거듭제곱은 특수한 형태가 아니면 일일이 반복해서 연산을 해야합니다.
어차피 반복해서 할거면 좀 더 간단하게 연산하는게 낫지 않을까요?
그러면 위 식을 좀 풀어봅시다.
아까 1번의 상태 전이가 이루어진 상태벡터는 전이행렬을 한번 곱해준 것과 같다고 했습니다.
$ \vec{v}^{(1)} = \mathbb{A} \cdot \vec{v}^{(0)} $
그렇다면 반복해서 
$ \vec{v}^{(2)} = \mathbb{A} \cdot \vec{v}^{(1)} $
$ \vec{v}^{(3)} = \mathbb{A} \cdot \vec{v}^{(2)} $
$ \vec{v}^{(4)} = \mathbb{A} \cdot \vec{v}^{(3)} $
이렇게 쓸 수 있겠죠?
 
이러면 연산량이
그냥 전이 행렬을 제곱할 때: 내적 9번
상태벡터로 계산할 때: 내적 3번
으로 1/3 줄어듧니다.
그럼 이걸 4번 반복해서 연산할경우 연산량이 확 줄겠죠?
 
그러나 아직 내적(곱의 합)을 계속 반복해야하는 단점이 있습니다.
그러면 이것 조차도 극복할 수 있을까요?
 
 

6. 상태벡터와 희소행렬의 정의를 이용해서 연산을 최적화하기

결론적으로 먼저 얘기해보자면, "네 가능합니다"입니다.
그럼 어떻게 이게 가능할까요?
 
위에서 살펴봤듯이 이 행렬을 보면 정말 특이한 희소행렬입니다.
삼중대각행렬인데, 그 중 주대각성분(main diagonal entries)이 0이며, 다른 두 상/하대각성분은 1인 굉장히 독특한 희소행렬이죠.
그렇다면 왠지 이 특성을 살려볼 수 있지 않을까요?
 
일단 $ \vec{v}^{(k+1)} = \mathbb{A} \cdot \vec{v}^{(k)} $를 한번 분해해봅시다.
아까 상태벡터는 각 요소가 h=0~n의 경우의 수를 나타낸다고 했습니다.
그러면 상태벡터의 각 h요소는 다음과 같이 계산될 것입니다.
$ \vec{v}^{(k+1)}_h = \mathbb{A}_{h,*} \cdot \vec{v}^{(k)} $
여기서 *은 모든 인덱스를 나타냅니다.
그리고 다시 이 행렬 연산을 요소별 연산으로 바꿔 나타내면,
$ \vec{v}^{(k+1)}_h = \sum \limits _j \mathbb{A}_{h,j} \cdot \vec{v}^{(k)}_j $
이와 같죠.
 
하지만 전이행렬 $ \mathbb{A} $는 희소해서 대부분의 $ \mathbb{A}_{h,j} = 0 $이며, 값이 있어 실제로 연산을 수행할 수 있는 부분은 '상대각요소'와 '하대각요소' 두 부분밖에 없죠.
따라서 살아있는 항만 남기면:
$ \vec{v}^{(k+1)}_h = \underbrace{\mathbb{A}_{h,h-1}}_{하대각요소} \cdot \vec{v}^{(k)}_{h-1} + \underbrace{\mathbb{A}_{h,h+1}}_{상대각요소} \cdot \vec{v}^{(k)}_{h+1} $
여기서 각 대각요소는 무조건 1의 값만 가지므로,
$ \vec{v}^{(k+1)}_h = \vec{v}^{(k)}_{h-1} + \vec{v}^{(k)}_{h+1} $
이렇게 간단히 덧셈계산만으로 해결이 됩니다.
여기서 h=0인경우와 h=n인 경우엔 index가 정의되지 않습니다.
여기서 index가 벗어나는 경우는 0으로 처리해주면 아래와같은 조건식으로 정리할 수 있습니다.
$ \vec{v}^{(k+1)}_h = \begin{cases} \vec{v}^{(k)}_{h+1} & \mathrm{if} \ h=0 \\ \vec{v}^{(k)}_{h-1} + \vec{v}^{(k)}_{h+1} & \mathrm{if} \ 0 < h < n \\ \vec{v}^{(k)}_{h-1} & \mathrm{if} \ h=n \end{cases} $
 
한번 실제로 계산해볼까요?
n=2일때로 진행해봅시다.
전이행렬 $ \mathbb{A} $는
$ \mathbb{A} = \begin{bmatrix} 0&1&0 \\ 1&0&1 \\ 0&1&0 \end{bmatrix} $
초기 상태벡터는 $ \vec{v}^{(0)} = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} $ 이와같을 겁니다.
그럼 첫번째 전이 이후의 상태벡터 $ \vec{v}^{(1)} $는
$ \vec{v}^{(1)} = \begin{bmatrix} 0&1&0 \\ 1&0&1 \\ 0&1&0 \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} $
이렇게 볼 수 있겠죠?
여기서
$ \vec{v}^{(k+1)}_h = \underbrace{\textcolor{red}{\mathbb{A}_{h,h-1}}}_{하대각요소} \cdot \textcolor{red}{\vec{v}^{(k)}_{h-1}} + \underbrace{\textcolor{blue}{\mathbb{A}_{h,h+1}}}_{상대각요소} \cdot \textcolor{blue}{\vec{v}^{(k)}_{h+1}} $
$ \vec{v}^{(k+1)}_h = \begin{cases} \vec{v}^{(k)}_{h+1} & \mathrm{if} \ h=0 \\ \vec{v}^{(k)}_{h-1} + \vec{v}^{(k)}_{h+1} & \mathrm{if} \ 0 < h < n \\ \vec{v}^{(k)}_{h-1} & \mathrm{if} \ h=n \end{cases} $
이 정의를 한번 사용해봅시다.
일단, h=0에서 봅시다
$ \vec{v}^{(1)}_{0} = \begin{bmatrix} \textcolor{green}{\lbrack}&\textcolor{red}{0}&\textcolor{green}{1}&\textcolor{blue}{0}&\textcolor{green}{\rbrack} \\ & 1&0&1 & \\ &0&1&0 \end{bmatrix} \cdot \begin{bmatrix} \textcolor{red}{1} \\ 0 \\ \textcolor{blue}{0} \end{bmatrix} $
$ \vec{v}^{(1)}_{0} = [\ 0\ ]$
h=1에서는
$ \vec{v}^{(1)}_{1} = \begin{bmatrix} &0&1&0 \\ \textcolor{green}{\lbrack}& \textcolor{red}{1}&\textcolor{green}{0}&\textcolor{blue}{1} &\textcolor{green}{\rbrack} \\ &0&1&0 \end{bmatrix} \cdot \begin{bmatrix} \textcolor{red}{1} \\ 0 \\ \textcolor{blue}{0} \end{bmatrix} $
$ \vec{v}^{(1)}_{1} = [\ 1\ ]$
h=2에서는
$ \vec{v}^{(1)}_{2} = \begin{bmatrix} &0&1&0 \\ & 1&0&1 & \\ \textcolor{green}{\lbrack}&\textcolor{red}{0}&\textcolor{green}{1}&\textcolor{blue}{0}&\textcolor{green}{\rbrack} \end{bmatrix} \cdot \begin{bmatrix} \textcolor{red}{1} \\ 0 \\ \textcolor{blue}{0} \end{bmatrix} $
$ \vec{v}^{(1)}_{2} = [\ 0\ ]$
최종적으로
$ \vec{v}^{(1)} = \begin{bmatrix} 0 \\ 1 \\ 0 \end{bmatrix} $
네, 실제 행렬 연산 결과와 같네요!
그럼 $ \vec{v}^{(2)} $는 그냥 바로 정의대로 계산해볼까요?
$ \vec{v}^{(2)}_0 = \vec{v}^{(1)}_1 = [1] $
$ \vec{v}^{(2)}_1 = \vec{v}^{(1)}_0 + \vec{v}^{(1)}_2 = [0] $
$ \vec{v}^{(2)}_2 = \vec{v}^{(1)}_1 = [1] $
$ \vec{v}^{(2)} = \begin{bmatrix} 1\\0\\1 \end{bmatrix} $
와.. 이제 2번째 상태벡터를 구했네요...
그럼 이제 계산도 하나하나 해봤으니 이제 바로 결과만 보겠습니다.
$ \vec{v}^{(3)} = \begin{bmatrix} 0\\2\\0 \end{bmatrix} $
$ \vec{v}^{(4)} = \begin{bmatrix} 2\\0\\2 \end{bmatrix} $
여기서 h=0인 첫번째 요소만 보면 바로 2이고, 이것은 바로 $ C_2 $값과 같네요!
 
길고 긴 여정이었지만..

이러한 구조를 이용하면, 선형대수적 계산만으로도(특히나 덧셈의 반복연산만으로도) 카탈란수를 구할 수 있습니다!
 
 

7. 결론

정리하자면, n번째 카탈란 수는
$ \vec{v}^{(k+1)}_h = \begin{cases} \vec{v}^{(k)}_{h+1} & \mathrm{if} \ h=0 \\ \vec{v}^{(k)}_{h-1} + \vec{v}^{(k)}_{h+1} & \mathrm{if} \ 0 < h < n \\ \vec{v}^{(k)}_{h-1} & \mathrm{if} \ h=n \end{cases} $
이와 같은 상태벡터의 반복 업데이트로 구할 수 있습니다.
 
특히나 전이행렬의 특이한 성질로 인하여 위 식을 유도한 뒤에는, 전이행렬을 정의할 필요 없이 초기 상태벡터의 정의 이후 n번의 상기 규칙의 업데이트만으로 카탈란 수를 구할 수 있다는 것이 아주 독특한 결론이네요!
 

8. 의의와 한계

* 의의

• 비선형 점화식이었던 카탈란 수열을, Dyck path의 전이 구조로 선형대수적 모델링에 성공했습니다.
• 희소행렬과 상태벡터를 이용하여, 곱의 합(내적)같은 복잡한 연산 심지어는 단순 곱셈조차도 없이 단순 덧셈만으로 카탈란 수를 구할 수 있게 되었습니다.

* 한계

• n번째 카탈란수를 구하려면 2n번 순차적으로 상태벡터를 업데이트해야 합니다.
• 카탈란수의 일반항은 선형대수로는 풀 수 없습니다.

9. 더 알아보기

사실 흥미롭게도, 위에서 모델링한 전이행렬 $ \mathbb{A} $는 Toeplitz 행렬이라고 불리는 특정한 형태의 행렬과 매우 유사한 구조를 가집니다.
Toeplitz 행렬은 각 대각선(왼쪽 위에서 오른쪽 아래로 내려가는 방향)의 원소가 모두 같은 행렬을 말하는데,
여기서는 주대각선이 0, 상하대각선이 1로 채워진 삼중대각행렬 형태를 띠고 있죠.

이는 곧, 이 행렬이 상태벡터에 대해 [1, 0, 1] 형태의 커널을 가지는 convolution 연산을 수행하고 있다는 뜻이기도 합니다.(행렬에서 확인하실 수 있듯이 맨 처음과 끝에 커널의 한쪽을 잘라 연산하면 크기가 동일한 convolusion vector를 얻을 수 있습니다.)[엄밀히는 cross-correlation 방법이지만요.. 커널 형태가 뒤집어도 동일하니 convolusion이라고 봐도 무방하기도하고..]
다시 말해, 각 단계에서 상태벡터는 인접한 두 값의 합으로 갱신되며, 이는 일종의 필터링 또는 합성곱 연산으로 해석할 수 있습니다.

물론 Toeplitz 행렬과 convolution의 정확한 관계를 깊이 있게 탐구하려면 다소 복잡한 내용이므로, 이 포스팅에서는 그 가능성에 대한 화두를 던지는 정도로 마무리하겠습니다.

10. 총평

이처럼 카탈란 수는 조합적 정의, 생성함수, 역함수 정리뿐 아니라, 선형대수의 관점에서도 풀어낼 수 있는 문제입니다.
이 방식은 일반항 도출에는 적합하지 않지만, 구조적 이해와 계산 방법, 알고리즘 구현에서 강점을 지니고 있습니다.(특히나 덧셈의 반복계산은 코딩문제에 아주 적합하죠)
정말 이것으로 찐 카탈란 수 시리즈를 마무리 짓겠습니다!
따라오시느라 수고 많으셨습니다!

라그랑주 역함수 정리(Lagrange Inversion Theorem)

📘 카탈란 수열 시리즈

• 🌱 카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?
• 🔢 카탈란 수열의 일반항 구하기: 조합으로 구하기
• 🧮 카탈란 수열의 점화식 구하기
• 📐 카탈란수의 응용: n+2각형에서 삼각형으로 분할하기
• 🧪 카탈란 수열의 일반항을 생성함수로 구해보자 (1)
• 🧰 이항정리를 이항급수로 확장하기
• 🔍 카탈란 수열의 일반항을 생성함수로 구해보자 (2)
• 🔄 라그랑주 역함수 정리 (Lagrange Inversion Theorem)
• 🧠 번외: 카탈란 수를 선형대수로 풀 수 있다고?

1. 라그랑주 역함수 정리(Lagrange Inversion Theorem)

'라그랑주 역함수 정리' 용어자체가 생소하신 분들이 많으실거라 생각합니다.

혹여는 'Inversion'을 '역함수'라고 안보고 그냥 '반전'이라고 번역해서 '라그랑주 반전 정리'라고도 쓰이더군요.

그러나 '라그랑주'는 아주 다들 친숙하실테죠?

지구과학이나 물리에서 나오는 '라그랑주 점'도 이 분 이름이고 말이죠...

살면서 한번은 듣게되는 이름 중 하나가 아닐까 싶습니다.

아 물론 사람이구요, 위대한 인물이시죠.

[뭐 라플라스, 푸리에, 뉴턴, 오일러, 가우스 뭐 이런사람들 있잖아요... 심지어 저번 포스팅의 코시곱도 코시라는 사람이름이에요..]

뭐 사실 이 포스팅을 쓰는 순간조차도 저는 저 라그랑주 역함수 정리의 전체 형상을 모릅니다.

그저 그 정리의 결과로써 도출되는 내용과 그걸 어떻게 사용할 수 있는지 정도만 어렴풋하게 알고있는 수준입니다만,

제가 이걸 왜 포스팅에 쓰게 되었냐면,

이 정리를 이용하면 진짜 아주 쉽게 비선형 점화식을 가진 수열을 풀 수 있거든요.

라그랑주 역함수 정리는 결과적으로 '어떤 함수의 역함수를 멱급수로 전개했을 때, 각 항의 계수를 직접 계산할 수 있도록 해주는 정리'입니다.

2. 카탈란 수열의 생성함수에의 적용

바로 얼마전까지 진짜 온몸을 비틀어가며 간신히 생성함수로부터 이항급수를 통해 카탈란수의 일반항을 구했었는데요(누가 시키지도 않았었지만..)

이때, 생성함수가 자기자신을 포함한 '암시적'인 형태로 나왔었죠.(여기서 말하는 명시적vs암시적 함수라는 뜻은 f(x)=x처럼 깔끔하게 x로 정의되는 함수가 '명시적 함수', f(x) = xg(f(x))처럼 f(x)자체가 자신을 포함한 구조로 정의되는 함수가 '암시적 함수'라고 합니다)

물론 간단한 조작으로 이걸 다시 명시적 함수로 바꾼뒤 그 뒤를 진행했지만,

여기서 바로 라그랑주 역함수 정리를 이용하면

'암시적으로 정의된 함수의 생성함수를 "역함수로 본 다음" 그 멱급수 전개를 추출'하게 됩니다.

즉, $ C(x) $가 무엇인지 바로 찾는게 아니라,

우리가 구하려는 생성함수 C(x)가 어떤 함수 F의 역함수라고 보고 F(C(x)) = x 꼴로 놓는다면, 역함수 정리를 통해 C(x)를 추출할 수 있다는 것이죠.

다시말해,

$ xC(x)^2 - C(x) + 1 = 0 $에서 오히려

$ x = \frac{C(x) - 1}{C(x)^2} $ 꼴로 놓고

$ x = F(C(x)) $ 이런 식으로 본 다음에, 역함수를 취해

$ F^{-1}(x) = C(x) $로 만듧니다.

여기서 어떤 함수 $ F(x) $의 역함수 $ F^{-1}(x) = C(x) $를 멱급수로 전개했을 때, 그 항의 계수 $ C_n  $​을 직접 계산할 수 있게 해주는 정리가 바로 라그랑주 역함수 정리입니다.

(※ 생성함수의 멱급수 전개와 계수의 의미는 https://omnil.tistory.com/226, https://omnil.tistory.com/227에서 자세히 다뤘으니, 궁금하신 분은 그쪽을 참고해주세요!)

뭐, 결국 C(x)를 역함수로 보고, 이 역함수를 멱급수로 전개했을 때 특정 항의 계수를 알 수 있다는거죠.

그냥 원래 저희가 구하고 싶던거 구하는겁니다.

3. 형태는 어떻게 생겼는데?

라그랑주 역함수 정리는 다음과 같은 모양을 가졌습니다.

$ [x^n]f^{-1}(x) = \frac{1}{n}[t^{n-1}]\left(\frac{t}{f(t)}\right)^n \qquad (f(0) = 0, f'(0) \neq 0) $

여기서 대괄호 안에 있는 부분은 '거듭제곱이 n인 항을 찾겠다'는 뜻입니다.

(좀 더 자세하게는, $ [x^n]f(x) $란 표기는 멱급수 $f(x)=\sum a_kx^k $ 중 $a_n$을 의미합니다.)

말로 설명해보자면 "역함수의 $x^n$의 계수는 $\left(\frac{t}{f(t)}\right)^n$의 $t^{n-1}$의 계수를 n으로 나눈 값과 같다." 입니다.

그냥 정의자체가 이래요. 그리고 진짜로 풀면 답이 나오는게 신기하죠.

4. 라그랑주 역함수 정리의 다른 형태

그런데, 위와 같은 형식(standard form)에서는 계산을 하기가 조금 애매한 사항이 많습니다.

역함수가 분석적으로 존재하고 전개가 단순한 경우에는 저 형태도 굉장히 잘 작동하지만, 조합적 구조(재귀적 생성)를 가진 함수는

- $\frac{t}{f(t)}$ 자체가 복잡한 유리함수가 되기 쉽고
- 그것을 n제곱하면 차수가 급격히 상승하고
- 원하는 $ t^{n-1} $ 항이 존재하지 않거나, 매우 뒤에 등장하는 경우가 많기 때문에

저 형식을 사용하기 어려워지죠.

그러면 아예 답이 없냐고 하면, 식 자체를 재귀적 생성 형태(자기자신을 포함하는 형태)로 변형시키면 됩니다.(다르게 변형한 라그랑주 역함수 정리도 많습니다)

[[아래와 같은 변형을 Lagrange-Bürmann formula[라그랑주 뷔르만 공식]이라고 합니다.]]

$ y = x \cdot \phi (y) $

형태로 변형시키면, 이 변형에 해당하는 라그랑주 역함수 정리는

$ [x^n]y(x) = \frac{1}{n}[t^{n-1}]\phi(t)^n $

가 됩니다.

5. 역함수 정리의 변형 형태로 풀어보는 카탈란 수열

카탈란 수열을 예로 들어볼께요.

카탈란 수열의 생성함수는

$ C(x) = xC(x)^2 +1 $

이와 같고, 이를

$ y = x \cdot \phi(y) $ 형태로 바꾸면

$ C(x) - 1 = x \cdot C(x)^2 $ 과 같이 바꿀 수 있습니다. 여기서 바로 $ y = C(x)-1 $로 치환합니다.

그러면

$ y = x(y+1)^2 $처럼 정리가되고, 이는 바로 $ y = x \cdot \phi(y) $의 형태가 됩니다.

여기서 바로 역함수 정리를 적용하면

$ [x^n]y(x) = \frac{1}{n}[t^{n-1}]\phi(t)^n $

$ [x^n](C(x)-1) = \frac{1}{n}[t^{n-1}](t+1)^{2n} \quad (n \ge 1) $

이렇게 정리가 되겠죠?

여기서 $ C(x)-1 $의 의미는 생성함수에서 상수항을 제거한 조건(tail truncation)인데요, 말그대로 카탈란 수열의 재귀적 항들만 보겠다는 의미가 됩니다.

그래서 $ C_0 $를 따로 정의해줘야합니다. 식 자체도 n이 분모에 있기때문에 1부터 정의가 되니까 n=0인 상황은 따로 정의해줘야죠.

그리고 $ x^n $의 계수는 멱급수 정의에서 $ C_n $이었으므로, $ C_n $을 알고싶다면, $ x^n $의 계수를 찾으면 됩니다.

6. 구한 식으로 n = 2 계산해보기

그럼 간단하게 $ n=2 $인 상황을 봅시다. $ C_2 $값은 이미 2라는걸 저희는 알고있죠?

$ [x^2](C(x)-1) = \frac{1}{2}[t^1](t+1)^4 $

이렇게 식이 정리가 되겠고, 네제곱에서 지수가 1인 항의 계수는 이항정리에서 $ {_4} C_1 $이므로, 4가 되죠?

그러면

$ C_2 = \frac{1}{2} \cdot 4 = 2 $

오.. 바로 딱 나왔네요

7. 라그랑주 역함수 정리 식으로 일반항 구하기

그럼 이걸로 일반항도 유도할 수 있을까요? 뭔가 특정 수를 넣어주는 대신 주어진 그대로 n에대해 풀면 되지 않을까요?

이제 우항만 살펴봅시다

$ \frac{1}{n}[t^{n-1}](t+1)^{2n} $

여기서 2n승의 (1+x)에서 n-1승 항의 계수는

$ {_{2n}} C_{n-1} $이겠네요?

그럼 우항을 정리하면

$ \frac{1}{n}{_{2n}} C_{n-1} $

하나의 식이 나왔군요! 근데 어째 항상 저희가 보던 식의 모습이랑 조금 다릅니다?

그럼 식 변형을 한번 해볼까요?

일단 조합 공식은 다음과 같습니다.

$ {_n}C_r = \frac{n!}{r!(n-r)!} $

$ {_{2n}}C_{n-1} = \frac{(2n)!}{(n-1)!(2n-(n-1))!} = \frac{(2n)!}{(n-1)!(n+1))!} $

자, 여기서 $ \frac{1}{n} $까지 포함해서 식을 다시쓰면

$ \frac{(2n)!}{(n-1)!(n+1))! \cdot n} $

$ = \frac{(2n)!}{n!(n+1))!} \quad \because (n-1)! \cdot n = n! $

$ = \frac{(2n)!}{n!n! \cdot (n+1)} \quad \because (n+1)! = n! \cdot (n+1) $

$ = {_{2n}}C_n $

결국,

$ C_n = \frac{1}{n}{_{2n}} C_{n-1} = \frac{1}{n+1}{_{2n}}C_n = \frac{1}{n+1}\binom{2n}{n} $

으로 정리가 되면서, 일반항이 풀립니다.

그러나 여기서 $ n=0 $인 경우는 예외로 두었기 때문에 엄밀하게는 구간을 나눠서

$ C_n = \begin{cases} \frac{1}{n+1}\binom{2n}{n} \quad n \ge 1 \\ 1 \qquad n = 0 \end{cases} $

이렇게 보아야하지만, 식이 정리되면서 일반항이 n=0인 것까지 포함을 할 수 있게 되면서

$ C_n = \frac{1}{n+1}\binom{2n}{n} $이라는 일반항을 라그랑주 역함수 정리로 유도할 수 있었습니다.

8. 결론

사실 뭔가 빙빙 돌아왔지만, 개념만 알고있으면 공식을 통해 특정 항의 계수를 바로 알아내거나 심지어는 아주 빠르게 일반항을 뽑아낼 수 있는 강력한 공식이 바로 라그랑주 역함수 정리입니다.

카탈란 수열의 일반항을 생성함수로 구해보자(2)

📘 카탈란 수열 시리즈

• 🌱 카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?
• 🔢 카탈란 수열의 일반항 구하기: 조합으로 구하기
• 🧮 카탈란 수열의 점화식 구하기
• 📐 카탈란수의 응용: n+2각형에서 삼각형으로 분할하기
• 🧪 카탈란 수열의 일반항을 생성함수로 구해보자 (1)
• 🧰 이항정리를 이항급수로 확장하기
• 🔍 카탈란 수열의 일반항을 생성함수로 구해보자 (2)
• 🔄 라그랑주 역함수 정리 (Lagrange Inversion Theorem)
• 🧠 번외: 카탈란 수를 선형대수로 풀 수 있다고?

1. 서론

네, 불가피하게? 카탈란 수열의 일반항을 생성함수로 구해보자 두번째 시간입니다...!

저번 포스팅까지 카탈란 수열의 생성함수를 구해보았는데요, 이번 포스팅에서는 이렇게 구한 생성함수로 일반항을 끌어내 보도록 하겠습니다.

이번 포스팅은 제발 길어지지 않기를...

2. 생성함수에서 어떻게 일반항을 끌어내는데?

자 여기서 제일 중요한 부분입니다.

생성함수를 왜 사용하는지는 저번 포스팅에서 깔끔하게 정리했습니다.

자, 그러면 이 생성함수를 써서 압축한 정보를 어떻게 다시 변형하여 unzip할거냐!

바로 '멱급수를 써서 압축했으니, 멱급수 형태로 다시 표현되면 unzip이겠네?'입니다.

큰 맥락은 다음과 같습니다.

1) 무한한 수열을 무한한 멱급수의 계수에 대응시킵니다.

2) 그리고 이걸 '너는 이제부터 생성함수여'하면서 생성함수를 한줄의 수식으로 이쁘게 정리합니다.

3) 이렇게 정리된 수식은 이제부터 씹고 뜯고 맛보고 즐길 수 있는 형태가 된 것입니다. 그러니 열심히 조작을 가합니다.

4) 이렇게 조작이 가해져 이젠 형체조차 알아볼 수 없게 된 친구를 다시 멱급수의 형태로 바꿉니다.

5) 오잉? 멱급수의 $ \sum $와 $ x^n $사이에 전혀 새로운 형태가 생성됩니다

6) 오호 이 수열을 나타내는 다른 방식(= 일반항)이 바로 너구나!

이렇게 진행되는 겁니다.

그리고 저번 포스팅까지 우리는 3번까지 한겁니다.

조작을 가하던 중간에 일단 한숨 돌린셈이죠. 일단 명시적인 생성함수를 찾았으니까요.

이번의 포스팅은 4번부터 시작입니다.

이렇게 조작된 생성함수를 다시 멱급수의 형태로 바꿀겁니다.

그러면 일반항의 모양이 나오겠죠?

그러면 계수만 따로 떼서 이 수열의 일반항은 너여! 이러면 끝나는 겁니다

3. 생성함수를 이항급수로 나타내기

일단 저번 포스팅의 결과를 다시 끌어오죠

$ C(x) = \frac{1-\sqrt{1-4x}}{2x} $

자 여기서 어떻게 하면 다시 '무한급수'형태로 다시 바꿀 수 있을까요?

$ (1+x)^n $을 이산적으로 풀어낸 이항정리에서 이걸 무한급수로 풀어낸 이항급수로의 변환을 기억하고 계실까요?(https://omnil.tistory.com/223)

왠지 이걸로 '무한급수'형태를 만들 수 있을 것 같지 않나요?

마침 저기 식에도 비슷한 꼴이 보입니다. 루트는 $ \frac{1}{2} $승이라고 볼 수도 있으니까,

$ (1+(-4)x)^\frac{1}{2} $

이 친구가 이항급수의 꼴이네요~

그러면 바로 슉슈슉슉 조작을 가해볼까요?

이항급수는 아래와 같은 식으로 정의됩니다.(다시한번 포스팅을 보고오셔도 좋습니다: https://omnil.tistory.com/223)

$ (1+x)^n = \sum \limits _{k=0} ^\infty \frac{1}{k!} \prod_{i=1}^{k} (n - i + 1) x^k = \sum \limits _{k=0} ^\infty \binom{n}{k} x^k $

[ 그리고 여기서 $ k=0 $항과 $ k=1 $항은 독특하게 정의됨을 알 수 있습니다.

애초에 $ k=0 $항은 곱셈구간이 정의되지 않으므로 무조건 1이 나오며, $ k=1 $항은 무조건 계수가 $ n $이 나오는 걸 알 수 있죠. ]

이제 위 식에 대입해보면

$ (1+(-4)x)^\frac{1}{2} = \sum \limits _{k=0} ^\infty \binom{\frac{1}{2}}{k} (-4x)^k = \sum \limits _{k=0} ^\infty \frac{\frac{1}{2}\left(-\frac{1}{2}\right)\cdots\left(\frac{1}{2}-k+1\right)}{k!}(-4x)^k $

가 되고, 풀어쓰면

$ 1 + \frac{1}{2}(-4x) + \frac{\frac{1}{2}\left(-\frac{1}{2}\right)}{2!}(-4x)^2 + \cdots $

부호는 상수항을 빼고는 전부 마이너스 부호가 나옵니다.

- 거듭제곱이 홀수면 거듭제곱의 부호는 음수이지만, 계수에서의 부호가 양수이므로 마이너스

- 거듭제곱이 짝수면 거듭제곰의 부호는 짝수이지만, 계수에서의 부호가 음수이므로 마이너스

이기 때문이죠.

결국 제일 초항인 상수항 만을 제외하고 전부 마이너스로 묶으면 이제 부호는 신경쓸 필요가 없어진단 말이겠군요.

그렇다면 이부분을 부호상관없이 바꿔보겠습니다.

$ \frac{1}{2}-k+1 $ 여기에 절대값을 취하면(부호상관 없어졌으니 다 양수로 갈음합니다)

$ \frac{\vert 1-2k+2 \vert}{2} =  \frac{2k-3}{2} $ ($ k \ge 2 $에서 양수가 나오게 수식 변형합니다. $ k = 1 $은 위에서 봤듯이 무조건 $ n $입니다.)

그러면 주어진 수식은 다음과 같이 변형됩니다.

$ 1 - \frac{\frac{1}{2}}{1!}(4x) - \sum \limits _{k=2} ^\infty \underbrace{ \frac{\frac{1}{2}\frac{3}{2}\cdots\left(\frac{2k-3}{2}\right)}{k!}(4x)^k } $

수식을 다 쓰기가 힘드니까 underbrace한 부분만 따로 떼놓고 봅시다.

$ \frac{\frac{1}{2}\frac{3}{2}\cdots\left(\frac{2k-3}{2}\right)}{k!}(4x)^k $

분모를 따로 빼고, 분자의 모습을 보면

분자에서 분모는 무조건 2인 상태로 k번 반복해서 곱해지고 있으므로 $ 2^k $입니다.

$ \frac{1}{k!}\frac{1\cdot3\cdot\ ... \  \cdot (2k-3)}{2^k} 2^{2k}x^k $

수식 정리하면

$ \frac{1\cdot3\cdot\ ... \  \cdot (2k-3)}{k!} 2^{k}x^k $

분자를 잘 보면 1, 3, 5, ..., 2k-3 으로 홀수로 증가하고 있습니다.

뭔가 조작을 가해주면 아주 깔끔하게 팩토리얼로 표현할 수 있을 것 같은데 말이죠...

바로... 빈 짝수들을 끼워넣어주면 되겠네요!

2, 4, 6, ..., 2k-2을 사이사이에 넣어주면 왠지 (2k-2)!할 수 있겠죠?

짝수들은 다 2가 곱해진 형태이고, 2를 다 나눠주면 자연수랑 같아지잖아요? 그렇다면..

$ 2^{k-1}(1\cdot2\cdot...\cdot (k-1)) $ 요렇게 정리가 되겠고.. 뒷부분은 간단하게 다시 팩토리얼로 정리가능하겠네요

$ 2^{k-1}(k-1)! $

입니다.

자, 이제 끼워넣어 줍시다.

잘 보면 이미 식에 $ 2^k $가 있죠?

분모분자에 같은 식을 곱해줍시다.

$ \frac{1\cdot3\cdot\ ... \  \cdot (2k-3)(k-1)!2^{k-1}}{k!(k-1)!} 2x^k $

$ \frac{(2k-2)!\cdot2}{k!(k-1)!} x^k$

다시 전체 식을 써주면

$ 1 - \underbrace{\frac{\frac{1}{2}}{1!}(4x)}_{1} - \sum \limits _{k=2} ^\infty \underbrace { \frac{2(2k-2)!}{k!(k-1)!} x^k }_{2}$

자, 근데 이제 2번 underbrace를 잘 봐봅시다.

여기서 $ k = 1 $인 상황을 한번 봐볼까요?

$ \frac{2 * 0!}{1!0!}x = 2x $

어? 1번 underbrace와 같군요!

아하~ 아까는 부호문제로 포함하지 못했던 $ k=1 $도, 수식이 정리되고 나니 한꺼번에 합칠 수 있겠네요!

그렇게 다시 쓰면

$ (1+(-4)x)^\frac{1}{2} = 1 - 2\sum \limits _{k=1} ^\infty \frac{(2k-2)!}{k!(k-1)!} x^k $

여기서, $ k $는 1부터 시작하는데, 우리는 처음에 멱급수 0부터 시작했었으니까 index조정해줍시다.

지금까지 따라오시면서 index조정은 이제 일도 아니시잖아요들?



$ (1+(-4)x)^\frac{1}{2} = 1 - 2\sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^{k+1} $


자, 그럼 이제 생성함수 $ C(x) $에 이걸 대입시켜 정리하도록 하죠!



$ C(x) = \frac{1-\sqrt{1-4x}}{2x} = \frac{1}{2x} \left(1- \underline{(1+(-4)x)^\frac{1}{2}}\right) $

$ = \frac{1}{2x}\left(1-\left(1 - 2\sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^{k+1}\right)\right) $

$ = \frac{1}{2x} 2\sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^{k+1} $

$ = \frac{1}{2x} 2x\sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^k $

$ = \sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^k $

와우! 뭔가 엄청 깔끔하게 정리가 되었습니다!

4. 무한급수 형태에서 계수를 꺼내기

그럼 다시 처음에 저희 카탈란 수열의 생성함수를 정의하던 순간으로 돌아가볼까요?

$ C(x) = \sum \limits _{k=0} ^\infty C_k x^k $

오 그렇다면

$  \sum \limits _{k=0} ^\infty C_k x^k = C(x) = \sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^k $

$  \sum \limits _{k=0} ^\infty C_k x^k = \sum \limits _{k=0} ^\infty \frac{(2k)!}{(k+1)!k!} x^k $

자, 여기서 저희는 수열이 궁금했었어서 멱함수에 대응시켜줬었죠? 그러면 멱함수 부분을 떼버리고 계수만 본다면?

$  C_k = \frac{(2k)!}{(k+1)!k!} $

우와! 일반항을 구했습니다!

5. 일반항을 다시 정리

자 이 일반항을 다시 예쁘게 쓰면

가 되고, 이건 제일 처음 조합적 아이디어로 일반항을 구한 식과 완전히 동일합니다.(진짜 맞나 궁금해요? https://omnil.tistory.com/222)

완전 신기하지 않나요?

6. 미리니름

자, 사실은 앵간하면 점화식으로 정의된 수열의 일반항은 생성함수까지 오면 거의 끝이나 마찬가지인데요,

저는 여기서 한단계 더 나아가서 라그랑주 역함수 정리(Lagrange Inversion Theorem)까지 소개시켜드리도록 하겠습니다!

그리고 이번 포스팅도 엄청 길어졌네요...

다음에 보아요!

카탈란 수열의 일반항을 생성함수로 구해보자(1)

📘 카탈란 수열 시리즈

• 🌱 카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?
• 🔢 카탈란 수열의 일반항 구하기: 조합으로 구하기
• 🧮 카탈란 수열의 점화식 구하기
• 📐 카탈란수의 응용: n+2각형에서 삼각형으로 분할하기
• 🧪 카탈란 수열의 일반항을 생성함수로 구해보자 (1)
• 🧰 이항정리를 이항급수로 확장하기
• 🔍 카탈란 수열의 일반항을 생성함수로 구해보자 (2)
• 🔄 라그랑주 역함수 정리 (Lagrange Inversion Theorem)
• 🧠 번외: 카탈란 수를 선형대수로 풀 수 있다고?

1. 서론

이미 우리는 카탈란 수열의 일반항을 조합적 아이디어로 구해보았습니다.
그러나 피보나치 수열의 일반항을 구하는 포스팅에서처럼, 사실 카탈란 수열도 여러가지 방법으로 구해볼 수 있을 것 같습니다
그래서 이번엔 카탈란 수열의 일반항을 생성함수로 구해보고자 합니다.

2. 생성함수?

일단 생성함수(generating function)란 사실 어떤 수열의 모든 정보를 단 하나의 식으로 압축한 zip 파일과도 같습니다. 겉으로는 한 줄의 함수식일 뿐이지만, 안에는 무한히 많은 항의 정보가 차곡차곡 저장되어 있죠.

그래서 부분적으로 이 생성함수에서 약간씩의 정보를 끌어낼 수는 있지만, 이 생성함수 자체로 뭔가 큰 의미를 직관적으로 끌어낼 수는 없죠.

말그대로 모든 수열의 정보를 쓴 종이를 꾸겨서 공으로 만들어 놓아('압축') 겉으로는 잘 안보이는 그런 현상과도 비슷합니다.
그러나 이 생성함수는 말 그대로 수열의 전체 정보를 담고있기때문에 살살살 잘 풀어내면(종이를 펴면) 의미있는 정보를 끌어낼 수 있답니다!

여기서 생성함수는 일반적으로 멱급수로 표현됩니다.(멱급수는 이전포스팅(https://omnil.tistory.com/206)에서 자세히 보실 수 있습니다)
이렇게 표현하는 이유는, 수열을 하나의 식으로 압축하는 데 그치지 않고,
미분, 적분, 곱셈, 대입 등 우리가 잘 아는 함수 조작을 통해 계수들의 성질이나 일반항을 효과적으로 분석할 수 있기 때문입니다.
즉, 멱급수는 단순한 ‘형식’이 아니라, 수열을 다루기 위한 강력한 도구인 셈이죠.

하지만 우리는 x의 값보다는 각 항의 계수를 중심으로 볼 것이기 때문에, 멱급수에서 중요한 수렴 반경과 같은 해석적 특성은 고려하지 않는 형식적 멱급수(formal power series)로 다룰 것입니다.

이때 사용되는 x는 실제로 어떤 수를 대입하기 위한 값이라기보다는 각 항의 계수를 표시해주는 기호나 색인 같은 역할만 할 뿐인거죠.

그래서 중간에 나오는 생성함수에서 x가 사용되긴 하지만, 해석학적으로 변형이 가해지거나 다른 숨은 뜻을 (일부러) 찾아내지 않는 한 직접 대입으로는 의미있는 값을 산출하지 않습니다.

결국 생성함수를 x라는 색인값으로 '변환•압축'하고 다시 의미있는 일반항으로 '변환•압축풀기'하면 자연스레 x는 사라지는 매개변수 같은, 정보를 꺼내기 위한 일종의 ‘열쇠’ 같은 존재일 뿐이며 우리가 관심 있는 건 언제나 계수들(=수열)이랍니다!

한가지 예를 들어볼까요?
모든 항이 1인 수열 $ a_n $을 생각해봅시다.
이를 멱급수로 표현해보면
$ G(x) = a_0x^0 + a_1x^1 + a_2x^2 + \cdots + a_nx^n + \cdots $
로 표현되고,
다시 정리해보자면
$ G(x) = 1 + x + x^2 + \cdots $로 정리될겁니다.

양변에 x를 곱하면 $ xG(x) = x + x^2 + \cdots $가 되고, 이는 원래 $ G(x) - 1 $과 같아지죠?

$ G(x) - 1 = xG(x) $
$ G(x) - xG(x) = 1 $
$ G(x) (1-x) = 1 $
$ G(x) = \frac{1}{1-x} $

이렇게 정리가 되겠죠?

즉, 아주 간단한 이 함수 하나가 $ a_n = 1 $이라는 수열 전체의 정보를 담고 있는 생성함수인 것입니다!

3. 카탈란 수열의 생성함수?

그러면 카탈란수열의 생성함수를 바로 구해볼까요?
일단 형식적 멱급수를 이용하여 카탈란 수열을 계수로 표현하면

$ C(x) = C_0 + C_1x + C_2x^2 + \cdots $
$ C(x) = \sum \limits _{n=0} ^{\infty} C_nx^n $

로 표현할 수 있겠습니다.

여기서 점화식이 선형조합으로 구성되어있다면 아주 단순한 조작만으로 생성함수를 정리할 수 있겠지만(피보나치 수열의 생성함수 포스팅(https://omnil.tistory.com/206)을 참조해주세요)

애초에 카탈란 수열의 점화식이 비선형 점화식이므로 간단하게 정리는 힘듦니다.

그럼 일단 점화식으로 다시 풀어서 써 볼까요?

$ C(x) = C_0 + \sum \limits _{n=1}^{\infty} \left ( \sum \limits _{k=0} ^{n-1} C_kC_{n-1-k} \right ) x^n $

$ C_0 $는 점화식에서도 정의가 없었으니까 따로 더해줍니다.

$ C(x) = C_0 + x \cdot \sum \limits _{n=1}^{\infty} \left ( \sum \limits _{k=0} ^{n-1} C_kC_{n-1-k} \right ) x^{n-1} $

자, summation식에서 $ x $하나를 빼줍니다. 그러고나서 n을 0부터 시작하는 모양으로 다시 바꿔주면,

$ C(x) = C_0 + x \cdot \underbrace{ \sum \limits _{n=0}^{\infty} \left ( \sum \limits _{k=0} ^{n} C_kC_{n-k} \right ) x^{n} } $

이렇게 나올겁니다.

근데, 우측항에서 underbrace된 부분이 뭔가 재밌지 않나요?

$ \sum \sum \sim x^n\  $은 뭔가 분해될 것 처럼 생기지 않았습니까?

네, 바로 코시곱(Cauchy product)라는 모양인데요, 두 무한 급수 $ \sum \limits _{n=0}^{\infty} a_n x^n $과 $ \sum \limits _{n=0}^{\infty} b_n x^n $의 곱은 $ \sum \limits_{n=0}^{\infty} \sum \limits _{k=0}^{n} a_kb_{n-k} x^n $ 급수와 같다는 정의입니다.(여기서 급수는 기본적으로 덧셈과 같으므로, 곱셈에 대하여 분배/결합법칙이 성립합니다. 즉, $ x^n $은 없어도 상관없는 항이지만 이해를 돕기위해 같이 썼습니다.)

그럼 이 정의를 따르게 되면, underbrace된 부분은

$ \sum \limits _{n=0}^{\infty} C_nx^n \cdot \sum \limits _{n=0}^{\infty} C_nx^n $이 되겠군요.

처음에 $ C(x) = \sum \limits _{n=0} ^{\infty} C_nx^n $이라고 정의하였으니 다시 정리하면

$ C(x) \cdot C(x) = C(x)^2 $으로 정리되겠네요!

그럼 다시쓰면

$ C(x) = C_0 + x C(x)^2 $

이고, 이걸 다시 방정식 형태로 정리하면, 아래와 같이 깔끔하게? 나옵니다.

$ xC(x)^2 - C(x) + 1 = 0 $



지금까지 유도해본게 뭔가 수학적으로 유도해 보았다면(뭔가 이상한 코시곱이란 것도 나오고...) 이젠 좀 더 쉽게? 좌충우돌 유도해보겠습니다.

생성함수를 잘 보면 x의 거듭제곱을 기준으로 수열의 항들이 배치되어있습니다.
위에서 x가 일종의 열쇠 같은, 색인 역할을 한다고 얼핏 말씀드렸는데요, 이것이 바로 그것입니다.
그래서 x를 곱하거나 나누는 행위는 이 색인을 앞으로 당기거나 뒤로 미는것과 같은 행위가 되죠.
더불어 상수배를 하거나 상수항을 더하는 행위는 수열 전체를 스케일링하거나 평행이동하는 것과 비슷하죠.

일반적으로 생성함수를 푼다는 것은 멱급수로 정의된 수열을
1) x에 대해 명시적 함수로 변환하거나
2) 또는 그것이 어려울 경우 자기자신을 포함하는 방정식(암시적 함수)으로 정리하는 과정을 뜻합니다.
이는 무한한 수열을 무한한 멱급수로 표현한 뒤, 다시 단 한줄의 수식으로 변환/압축하는 과정이죠.

그리고 이 과정에서 자주 사용하는 테크닉들이 바로 위에서 말했던, x 차수 변환/상수배/상수항정리 등의 연산입니다.
이런 방법들을 통해 x에 대한 명시적 함수를 얻을 수 있다면, 더할나위 없이 쉽게 이후 과정이 진행되지만, 그렇지 않은 경우엔 암시적 함수가 되어서 조금 복잡해지는데요...
여기서 잘 보면, 이 카탈란수의 생성함수는 단순히 x를 곱하거나 나누거나, 상수배하거나 상수항을 조정하는 등의 조작만으로는 풀리지 않을 것 같습니다.

결국 험한 길을 가야한다는 뜻이 되겠네요...

그렇다면, 일단 생성함수 $ C(x) = C_0 + C_1x + C_2x^2 + \cdots $를 점화식으로 한번 풀어봅시다.

$ C(x) = C_0 + C_1x + (C_0C_1+C_1C_0)x^2 + (C_0C_2+C_1C_1+C_2C_0)x^3 + \cdots $

이렇게 나오겠죠?

뭔가 어떤 조작도 불가능 해 보이지만, 딱 하나 뭔가 가능해 보일 것 같은게 있지 않나요?

$ (1 + 2x) $를 한번 제곱해볼까요?
$ (1 + 2x)(1 + 2x) = 1*1 + 1*2x + 2x*1 + 2x*2x = 1*1 + (1*2+2*1)x + 4x^2 $

$ (1 + 2x + 2x^2) $도 한번 제곱해볼까요?
$ (1 + 2x + 3x^2)(1 + 2x + 3x^2) = 1*1 + (1*2+2*1)x + (1*3+2*2+3*1)x^2 + 12x^3 + 9x^4 $

오.. 딱 제곱한 최고차항만큼 까지 계수가 조합적으로 구성됨을 알 수 있습니다.

그러면 결국 생성함수를 제곱하면, 다시 자기 자신이 튀어나오겠군요!?

$ C(x) = C_0 + C_1x + C_2x^2 + \cdots $
$ C(x)^2 = C_0^2 + (C_0C_1+C_1C_0)x + (C_0C_2+C_1C_1+C_2C_0)x^2 + \cdots $

이걸 다시쓰면 $ C_0 = 1 $이고, 점화식을 다시 수열로 바꿔주면

$ C(x)^2 = 1 + C_2x + C_3x^2 + \cdots $

가 되겠네요.

잘 보면, 우항에서 x를 한번 곱해주고 1더하면 완벽히 자기 자신으로 돌아오는 걸 확인할 수 있습니다.

식으로 쓰면

$ C(x) = xC(x)^2 + 1 $이네요!

마찬가지로 정리해보면

$ xC(x)^2 -C(x) +1 = 0 $

완전히 위에서 구한것과 같습니다!

4. 카탈란 수열의 생성함수를 구하자

자 그럼 위에서 구한 식을 정리해볼까요?
$ C(x) $에 대해서 근의 공식을 구하면 풀릴 것 같습니다. 여기서 $ x $는 상수처럼 놓고 풀어보죠

근의 공식은 
$ \frac{-b \pm \sqrt{b^2-4ac}}{2a} $입니다.

대입해보면
$ C(x) = \frac{1 \pm \sqrt{1-4x}}{2x} $

이렇게 정리되겠습니다.

여기서 근의 공식 때문에 생성함수가 두 개처럼 보이게 되는데요, 어떠한 경우에도 한 수열을 생성하는 멱급수(생성함수)는 단 하나만 존재합니다.(함수식의 표현은 다양하게 할 수 있지만($ x \ = \frac{x^2}{x} $), 본질은 무조건 하나($ x $)라는 겁니다.

그러면 둘 중에 뭐가 진짜 생성함수일까요?

자, 생성함수에서 x는 어떤 값을 대입하기 위한 것이 아닌 특정 색인만 제공하는 역할이라고 했습니다.
그러나 딱 하나 예외적인 경우가 있는데요. 바로 $ x=0$인 경우입니다.
애초에 생성함수(멱급수)의 정의에서
$ C(x) = C_0 + C_1x + C_2x^2 + \cdots $라고 쓰기로 한거 기억나시나요?

여기서 아주 재밌게도, $ x=0 $인 순간 의미있는 값이 나옵니다.
바로 딱 $ C_0 $값이 나온다는거죠.

$ C(0) = C_0 = 1 $

입니다.

그러므로 우리는 $x=0$을 가지고 저 생성함수가 1이라는 값을 가지는지 아닌지로 판별해보겠습니다.

근데... 매우 슬프게도 정리한 수식의 분모에 $ x $가 있어서 0을 직접 대입할 수 없습니다...

그럼 아예 못구하냐? 하면 극한이라는 방법이 있죠

일단 $ C(x) = \frac{1 + \sqrt{1-4x}}{2x} $부터 검증해보겠습니다.

$ \lim \limits_{x\rightarrow0} C(x) = \lim \limits_{x\rightarrow0} \frac{1 + \sqrt{1-4x}}{2x} $

이라고 수식을 쓸 수 있겠고... 극한으로 가면갈수록 이 값은...

$ C(0) = \frac{2}{0} = \infty $

무한대로 가겠네요... 그럼 일단 얘는 아니라는거고 그럼 무조건 다른 식이 생성함수라는건데.. 한번 검증해볼까요?

다른 식은 부호가 마이너스인 식입니다.

$ C(x) = \frac{1 - \sqrt{1-4x}}{2x} $

똑같이 극한을 취해주면

$ \lim \limits_{x\rightarrow0} C(x) = \lim \limits_{x\rightarrow0} \frac{1 - \sqrt{1-4x}}{2x} $

$ C(0) = \frac{0}{0} $ 꼴이 되네요.

그러면 우항을 수식정리해서 분모가 0이 아니게 해줍시다.

일단 유리화합시다. 분자 분모에 $ 1 + \sqrt{1-4x} $를 곱해줍시다.

$ \frac{1^2 - (1-4x)}{2x(1 + \sqrt{1-4x})} $

이렇게 정리가 되겠네요. 식을 정리해주면

$ \frac{4}{2(1 + \sqrt{1-4x})} $

다시 여기에 극한 취해줍시다.

$ \lim \limits_{x\rightarrow0} \frac{4}{2(1 + \sqrt{1-4x})} $

$ \frac{4}{2(1 + 1)} $

$ C(0) = 1 $

5. 결론

네!! 카탈란수의 생성함수는 바로바로~

$ C(x) = \frac{1 - \sqrt{1-4x}}{2x} $

이것이었습니다!!!!

6. 여담

와.. 원래 한번에 일반항까지 쭉 구해보려했는데, 이거 뭐 작성시간이 장난이 아니네요... 불가피하게 2부작으로 나눠서 진행하겠습니다..!

카탈란수의 응용: n+2각형에서 삼각형으로 분할하기

📘 카탈란 수열 시리즈

• 🌱 카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?
• 🔢 카탈란 수열의 일반항 구하기: 조합으로 구하기
• 🧮 카탈란 수열의 점화식 구하기
• 📐 카탈란수의 응용: n+2각형에서 삼각형으로 분할하기
• 🧪 카탈란 수열의 일반항을 생성함수로 구해보자 (1)
• 🧰 이항정리를 이항급수로 확장하기
• 🔍 카탈란 수열의 일반항을 생성함수로 구해보자 (2)
• 🔄 라그랑주 역함수 정리 (Lagrange Inversion Theorem)
• 🧠 번외: 카탈란 수를 선형대수로 풀 수 있다고?

1. 서론

저번 포스팅까지, 아주 기나긴 여정을 거쳐왔습니다. 키탈란 수가 뭔지부터 시작해서 일반항을 구하고 점화식까지 찾아봤었죠.
그러는 와중 어렵기도 하였지만, 아주 완벽하게 카탈란수의 점화식을 구해봤는데요
오늘은 본질적으로 '그래서 카탈란 수로 뭘 할 수 있는데?'에 대해 한가지 문제를 풀어볼까 합니다. 사실 그 전에 카탈란수는 여기저기 조합적 문제에서 답이 된다고 말씀드렸고, 간단하게 괄호치기 문제도 살펴보았으나 좀 더 본격적으로 문제를 하나 풀어보죠!

2. 삼각분할(Triangulation)[n각형을 n-2개의 삼각형으로 분할하기 = n+2각형을 n개의 삼각형으로 분할하기]

여러분은 n각형의 내각의 합을 아시나요?
예에에전에 얼핏 본 기억이 있지 않으신가요?
삼각형은 180도, 사각형은 360도... 어라? 규칙이 보이는 것도 같습니다?
네 바로 180(n-2)가 n각형의 내각의 합이죠!
그리고 이건 n각형을 n-2개의 (볼록다각형의 최소 단위인)삼각형으로 분할할 수 있으며, 이때 각 삼각형의 내각의 합은 무조건 180도가 되기때문에 간단하게 유도되는 식입니다.
다시말해 n+2각형을 n개의 삼각형으로 분해할 수 있다고 볼수도 있네요(n 위치만 조금 조정했습니다)
그렇다면, 여기서 문제!
삼각형으로 분할할 수 있는 경우의 수는 몇가지일까요!?
일단 삼각형은 단 한가지로밖에 분할이 안될 것 같고... 사각형은 어떻게 될까요?

사각형은

이렇게 두 가지 방법이 나올겁니다

그렇다면 오각형은요?

네, 요렇게 세가지 방법이 나오겠죠?
는 아닙니다!
잘 보시면 제일 왼쪽모양은 오른쪽에 사각형이 남아있고 위에서 봤듯이 이 사각형은 다시 두가지 방식으로 삼각형으로 나눌 수 있습니다.
제일 오른쪽 또한 마찬가지겠네요?
그래서 방법은 총 2+1+2로 다섯가지입니다.

어라..? 눈치빠르신 분들은 벌써 알아차리셨죠?
바로 카탈란수의 점화식 꼴이네요!!

쉽게 이해해보자면 두개의 점을 바닥에 두고 기준 변으로 잡은 뒤에 남은 n개 기준점에 순차적으로 삼각형을 그려보면서 그 뒤에 더 분할되는 부분이 있는지 보게 되는거죠!

기준점의 왼쪽과 오른쪽, 각각의 도형으로 분할하여 더 나눌 건덕지가 있는지 보는겁니다!

그래서 어떤 기준점 왼쪽에 아예 뭐가 없으면 $ C_0 $, 삼각형 하나 있으면(점 하나있으면) $ C_1 $ ... 이런식으로 보는거죠

그럼 육각형을 한전 카탈란수로 봐볼까요?

자, 제일 왼쪽그림(첫 번째그림)에서 삼각형 왼쪽은 점이 없죠?($ C_0 $), 그리고 오른쪽은 오각형, 그러니까 점이 3개 있습니다($ C_3 $)
= $ C_0C_3 $

두 번째그림은 왼쪽에 점 하나, 오른쪽에 점 두 개 있으니, $ C_1C_2 $네요

세 번째그림은 왼쪽에 점 두개, 오른쪽에 점 하나있으니 $ C_2C_1 $

네 번째그림은 왼쪽에 점 세개, 오른쪽에 점 0개 있으니 $ C_3C_0 $

모든 경우의 수를 합쳐주면 6각형(4+2각형)에서는
$ C_0C_3 + C_1C_2 + C_2C_1 + C_3C_0 $
즉, $ C_4 $군요

3. 결론

결국 n+2각형을 n개의 삼각형으로 나누는 경우의 수는 카탈란수의 점화식으로 나타나며, 결국 n번째 카탈란 수가 정답이 되겠네요!

의외로 신기하지 않나요? 뭔가 경우의수나 조합같지않은, 생뚱맞은 기하학 문제에서 이렇게 경우의 수와 카탈란 수열이 연관이 있다니요!

사실은 이거 진짜 쉽게 이해하기 어려운 부분입니다
그러나 이미 저번 포스팅에서 고생하며 구한 노력이 여기서 빛을 발하네요~

4. 미리니름

다음 번에는 아주 조금 어려운 주제를 들고와보겠습니다. 기대해주세요!

5. 여담

재미삼아 정 18각형으로 그려본 그림... 사실 원리만 알면 이렇게 n이 큰 다각형을 그릴 필요도 없지만요...

카탈란 수열의 점화식 구하기

📘 카탈란 수열 시리즈

• 🌱 카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?
• 🔢 카탈란 수열의 일반항 구하기: 조합으로 구하기
• 🧮 카탈란 수열의 점화식 구하기
• 📐 카탈란수의 응용: n+2각형에서 삼각형으로 분할하기
• 🧪 카탈란 수열의 일반항을 생성함수로 구해보자 (1)
• 🧰 이항정리를 이항급수로 확장하기
• 🔍 카탈란 수열의 일반항을 생성함수로 구해보자 (2)
• 🔄 라그랑주 역함수 정리 (Lagrange Inversion Theorem)
• 🧠 번외: 카탈란 수를 선형대수로 풀 수 있다고?

 
0. 서론

저번 포스팅까지 해서 카탈란 수열의 일반항을 아주 직관적으로 조합적 방식을 통하여 구해보았습니다.
사실 개인적으로는 이거보다 더 깔끔하게 설명할 수 있나!? 싶을 정도로 자화자찬하고 싶습니다만...
오늘은 카탈란 수열의 점화식에 대해서 살펴보겠습니다.

 
1. 카탈란 수열의 점화식?

사실상 '카탈란 수열에도 점화식이 있어!?'라는 질문이 처음 나오는게 너무나도 당연한 시작일 것이라고 생각합니다.
왜냐면 사실 카탈란 수(카탈랑 수) 라는 거 자체가 처음부터 수열을 만들기 위한 정의 자체가 아니었거든요.

원래는 '문제풀이'가 카탈란 수의 본질이라면 본질이라고 볼 수 있습니다.

첫 포스팅에서 알아볼때, 참 많은 문제들의 답안으로 카탈란 수열이 사용된다고 알아보았습니다.
다시 정리하자면 가장 독특한게 괄호치기 문제, 그리고 그 다음으로 볼록 n+2각형에서 n개의 삼각형으로 분할하는 경우의 수, 뒤크 경로(Dyck path) 풀이(딕 경로라고도 부르는데요, 카탈란 수열 구하면서 봤죠? 엄밀하게는 격자이동 없이 우상향, 우하향하는 경로를 Dyck path라고 합니다), 뒤크 문자열의 수, 원 위에 2n개 점 잡고 n개 선분 그릴때 교점 없이 긋는 방법의 수, n개의 노드를 가지는 이진트리 구성 방법의 수, 스택정렬 가능한 경우의 수 등 여러 조합론적 문제에서 답이 되는 수 입니다.
그리고 그만큼 '어떤 n에 대해서 어떤 경우의 수를 가지나~'하는게 카탈랑 수의 본질이죠.

그래서 사실 점화식도 이후에 유도된 것이라고 봐도 무방합니다.(애초에 점화식으로 정의된 수열이 아니걸랑요!)

따라서 애초에 점화식으로 정의되며, 수열을 기본적으로 정의로 가지는 피보나치 수열과는 차이가 있습니다.
그럼에도 불구하고 이 카탈란 수를 이용한 수열은 어떠한 규칙성을 가지고 수를 계속 만들어 내기 때문에 수열이라고 볼 수 있는거구요.

2. 점화식은 어떻게 구할까?

사실 위에서 수많은 예시를 들었고, 그 예시들을 가지고 문제를 풀다보면 점화식은 쉽게 도출됩니다.
오히려 점화식에 비해 일반항이 구하기 어려운 편인데, 그마저도 격자이동에서의 Dyck path를 구하는 문제로 보면 쉽게 구할 수 있죠.(그래서 이걸로 카탈란 수의 일반항을 먼저 구했었죠)
(점화식으로 쉽게 정의되어 만들어진 피보나치 수열이 오히려 일반항은 굉장히 어렵게 구해지던 거랑 정 반대죠?)

그럼 저런 수많은 예시들을 놓고 어떤 방법으로 구해야 가장 쉽게 구해질까!? 하면, 사실 괄호치기 문제가 제일 간단하게 구할 수 있습니다.
물론, Dyck path문제로도 구할 수 있는데 이거는 아주 약간의 기하학적 아이디어들이 들어가야하므로 먼저 괄호치기 문제로 귀납적으로 점화식을 구하고, 그 다음 구해보도록 하겠습니다.(심지어 기하학적 아이디어 없이 수열분해부터 들어가면 어렵습니다)

3. 카탈란 수열의 점화식을 구해보자

3-1. 괄호치기 문제

괄호치기 문제로 점화식을 구하는게 왜 쉬운지는, 이후에 Dyck path를 통해 구하면서 알아보기로 하고 일단 구해봅시다.

- 괄호가 아예없다면 보나마나 경우의 수는 1입니다. = $ C_0 $

- 괄호가 '(' 하나 ')' 하나 있다면 경우의 수는 1입니다 = $ C_1 $

- 괄호가 '(' 두개 ')' 두개 있다면 경우의 수는 2입니다 = $ C_2 $
    ()(), (()) 이렇게 되겠지요?
    여기서 첫 괄호가 열리고 닫히는걸 주목해 봅시다.
    첫 괄호가 열리고 나서 어쩌구 저쩌구 한 뒤에 닫힌 경우와 그 뒤의 경우를 나눠서 생각해보면
    * ()() 경우에는
        첫 괄호가 열린 뒤 아무것도 하지 않고 닫혔고, 그 뒤에는 괄호가 한번 열리고 닫혔습니다.
        첫 괄호가 열린 뒤 아무 것도 하지 않고 닫혔다 = $ C_0 $
        그리고 그 뒤에 괄호가 한번 열리고 닫혔다 = $ C_1 $
        동시에 일어났으니까 곱하기!
        결국 $ C_0 \cdot C_1 $
    * (()) 경우에는
        첫 괄호가 열린 뒤 괄호가 한번 열리고 닫히고나서 첫 괄호가 닫혔고, 그 이후에는 뭐 어떻게 할 괄호가 없네요.
        첫 괄호가 열린 뒤 괄호가 한번 열리고 닫히고 나서 첫 괄호가 닫혔다 = $ C_1 $
        이후에는 괄호가 없다 = $ C_0 $
        곱해서 나타내면 $ C_1 \cdot C_0 $
    그리고 이 두가지 경우를 더해서 경우의 수를 나타내면 $ C_0 \cdot C_1 + C_1 \cdot C_0 $
    결과는 2입니다!

여기서 왜 첫괄호가 열리고 닫히는건 신경도 안쓰냐! 하실 수 있는데, 카탈란 수의 구조에서 ‘( )’처럼 괄호를 열자마자 바로 닫는 경우는, 구조적으로 아무것도 하지 않고 본래 상태로 되돌아온 것과 같습니다.
점화식에서는 첫 괄호쌍이 닫히는 시점(즉, 원점으로 돌아온 시점)을 기준으로 경로를 나누기 때문에(첫 원점이 제일 중요합니다. 첫 원점 이후 상황은 카탈란 수로 바로 결정되거든요), ‘열자마자 닫는’ 경우는 앞부분에서 유의미한 구조를 형성하지 못하므로, 기저적으로 $ C_0 (=1) $에 해당하는, 의미 없는 기본 단위로 간주하는 것입니다.
좀 더 그럴듯한 이유는 이어지는 Dyck path 문제에서 한번 더 살펴보시죠!

- 이젠 각 괄호가 세개씩 있는 상황입니다.
()()()
()(())
(())()
(()())
((()))
자, 첫 괄호가 닫히는 시점이 중요하다고 했죠?
잘 보면 첫 괄호가 닫히는 시점이 세가지로 나뉘는 걸 알 수 있습니다.
첫괄호가 바로 닫히는 경우
첫 괄호안에 괄호가 하나 있는경우
첫 괄호안에 괄호가 두개 있는경우
이렇게 말이죠.
첫 괄호가 열리자마자 닫히면 구조적으로 $ C_0 $ 라고 하였습니다.
그리고 그 뒤를 보면 바로 위에서 했던 모양이 보이죠? $ C_2 $입니다.
첫 괄호가 바로 닫히는 경우 클리어했습니다.
그 다음 첫 괄호 안에 괄호가 하나 있는 경우를 보겠습니다.
첫 괄호 안에 괄호 하나는 $ C_1 $이겠군요? 그리고 그 뒤로 괄호 하나가 더 나오니 또 $ C_1 $입니다. 두번째 조건도 클리어!
첫 괄호 안에 괄호가 두개 있는 조건도 보겠습니다.
첫 괄호 안에 괄호가 두개니까(그리고 그 모양은 바로 위에서 살펴보았던 모양) $ C_2 $겠군요.
그리고 그 뒤에는 남은 괄호가 없으니 $ C_0 $겠어요..
그러면 결국 다 더하면 $ C_3 = C_0C_2 + C_1C_1 + C_2C_0 $ 겠네요! 값은 5구요!

그리고 여기서 '점화식'이라고 볼 수 있는 것이 나옵니다.

눈치 빠르시면 아시겠지만, 바로 이전까지 나왔던 카탈란 수가 다음 카탈란 수를 결정하고 있는게 보이시나요?

그리고 규칙성도 보이지 않습니까?

그럼 지금까지 살펴본 것을 바탕으로 귀납적으로 사고해봅시다.

만약 $ C_n $의 점화식을 본다면,

1) 첫 괄호가 닫히는 걸 기준으로, '앞 카탈란 수'와 '뒷 카탈란 수'의 곱을 구분한다고 볼 수 있으므로 항은 n개가 생성이 될겁니다.

2) '앞 카탈란 수'는 첫 괄호 내에 계속해서 괄호들이 한 쌍씩 추가 될 것이므로 $ C_0 $부터 $ C_{n-1} $까지 늘어나겠네요(첫 괄호에서 이미 한쌍을 사용하죠? 그래서 n-1까지만 늘어납니다.)

3) '뒷 카탈란 수'는 남는 괄호를 가지고 만들어지는 카탈란 수니까 첫 괄호에 한쌍을 사용하고 남는 괄호들로 만들어지므로 $ C_{n-1} $부터 $ C_0 $까지 줄어들겠네요!

수식으로 써보면

$ C_n = C_0 C_{n-1} + C_1C_{n-2} + \cdots + C_{n-2} C_1 + C_{n-1} C_0 $

가 되겠구요!

$ C_4 $로 한번 확인해볼까요?

$ C_4 = C_0 C_3 + C_1 C_2 + C_2 C_1 + C_3 C_0 $

카탈란수가 0항부터 3항까지 각각 1, 1, 2, 5의 값을 가지니까, 계산해보면

$ C_4 = 1*5 + 1*2 + 2*1 + 5*1 = 14 $

예, 정답이 나오네요! 점화식을 귀납적으로 잘 찾아낸 것 같습니다!

근데, 저렇게 덧셈을 주루룩 늘어놓으면 보기가 별로 좋지 않죠...?

그래서 우리는 summation으로 저것을 간단하게 표현해 볼 것입니다. 대문자 sigma죠!

규칙도 간단합니다. 0부터 n-1까지 커지는거 하나, n-1에서 0까지 작아지는거 하나!

$ C_n = \sum\limits_{k=0}^{n-1} C_k C_{n-1-k} $

이렇게 간단(?)하고 깔끔(?)하게 카탈란 수열의 점화식을 구해보았습니다!

사실, 곰곰이 생각해보면 맞는 말이긴 하지만, 그럼에도 귀납법으로 유추를 하기도 하고 왠지 설명이 조금 부족하다 싶은 부분이 있을 수도 있습니다.

그럼 이어서 Dyck path로 구하는 법을 보도록 하죠.

3-2. Dyck path 문제

이번에는 Dyck path의 구조적 성질을 활용해 연역적으로 점화식을 유도해보겠습니다.

기하학적으로 보면 제일 깔끔한 유도방식이 아닐까 싶네요.

그러나 여기서는 각 점별로 하나하나 생각해 주는 것도 필요하고, 더군다나 prime Dyck path, 최초 귀환 이라는 개념들이 새로 나오는게 문제지만요, 사실 뭐 별다른 개념도 아닙니다.

자, 일단 개념 들어갑시다!

1] 최초 귀환점

'최초 귀환점'이란건, (0,0)에서 출발해서 Dyck path를 따라가다가 제일 처음으로 y=x선이랑 만나는 지점을 '최초 귀환점'이라고 합니다.

R과 U가 짝이 맞으면 다시 처음부터 이동하는 것과 마찬가지라고 생각할 수 있으므로 '다시 돌아왔다'고 볼 수 있는데, 직감적으로 이해가 되시죠?[혹은 0에서 출발해서 R이 +1, U가 -1이라고 보면 R하고 U가 짝이 맞으면(+1 + (-1)) 다시 0이 되죠?]

출발점 (0,0)은 귀환점에 포함되지 않으며, 일반적으로 (1,1), (2,2), ..., (n,n)까지 n개의 귀환점이 생깁니다.

이 최초 귀환점을 기준으로 경로를 두 부분으로 분해할 수 있습니다:

• 최초 귀환점까지의 경로 (앞 구간)
• 그 이후부터 종점까지의 경로 (뒷 구간)

n=2인 격자에서 그림으로 보자면, (1, 1)과 (2, 2)가 최초귀환점이 됩니다.

2] prime Dyck path

prime이라는 단어는 '더이상 분해할 수 없는' 상황에 붙이는 단어인데(1과 자기자신 이외에는 나눠지지 않는 수가 소수(prime number)죠) 이를 통해 유추해보자면 'Dyck path 중 더이상 분해되지 않는 Dyck path다'라고 생각해 볼 수 있습니다.

이게 무슨말인고?하니.. n=2인 격자를 한번 생각해보죠.[바로 위에 이미지가 있죠?]

Dyck path는 두 가지가 있는데, 하나는 중간에 y=x선에 닿았다가 진행하는 경우이고, 하나는 닿지 않고 진행하는 경우입니다.

여기서 잘 생각해보면, y=x선에 닿은 Dyck path(왼쪽)는 y=x선에 닿은 점을 기준으로 앞쪽 Dyck path랑 뒤쪽 Dyck path로 분해할 수 있게 되겠죠?

그런데, 두번째인 오른쪽의 경우는 그냥 그 자체로 하나의 Dyck path이지, 다른 Dyck path들로 분해할 수 없죠?

그래서 바로 오른쪽과 같은 경로를 prime Dyck path라고 부릅니다.

결국 prime Dyck path란 처음 출발 이후 종점에 도착할 때까지 한번도 y=x선에 닿지 않으면서 이동하는 경로를 말하는 것이죠.

3] prime Dyck path의 개수 구하기

저번 포스팅의 기억을 한번 돌이켜 볼까요?

저번 포스팅에서 Dyck path의 경우의 수는 전체 경로에서 Dyck path를 위반한 경로를 빼서 구했었습니다.

그때 Dyck path를 위반한 경로는 어떻게 구했나요?

'y=x선을 넘어간 애는 위반한 애야 $ \leftrightarrow $ y=x+1선과 닿은 애는 위반한 애야'

라고, 새로운 선을 하나 추가해서 풀었었죠!

그럼 이 아이디어를 다시 차용해 봅시다.

prime Dyck path는 y=x 선에 닿지 않아야 합니다.(위에서 살펴봤듯이 닿으면, 그 점을 기준으로 분해가 된다고 했죠?)

그렇다면, y=x-1 아래에서만 움직이는 경로는 그 어떤 상황에서도 절대로 y=x선과 닿을 수 없겠죠?

그리고 y=x-1 아래에서만 움직이기 위해서는 처음 y=x-1 선 아래로 움직이는 R 한번, 그리고 y=x-1 선에서 종점으로 움직이는 U 한번이 필수적으로 필요하다고 볼 수 있겠습니다.

따라서 n x n 격자에서 prime Dyck path의 수는 (n-1) x (n-1)을 움직이는 Dyck path의 수와 같아집니다.

2 x 2 격자에서 prime Dyck path의 수는 1 x 1 Dyck path의 수 즉, $ C_1 = 1 $입니다.

3 x 3 격자에서 prime Dyck path의 수는 2 x 2 Dyck path의 수 즉, $ C_2 = 2 $입니다.

4 x 4 격자에서 prime Dyck path의 수는 3 x 3 Dyck path의 수 즉, $ C_3 = 5 $입니다.

4] 그렇다면 1 x 1 격자에서 prime Dyck path의 수는 어떻게 될까요?

여기서 위에서 살펴보았던 괄호치기에서 왜 맨처음 열고닫는 괄호는 생각하지 않는지에 대한 해답이 있습니다.

1>> 지금까지 구한 대로라면 0 x 0 Dyck path의 수 즉, $ C_0 = 1 $이어야 합니다.(그리고 이 결과는 썩 괜찮은 논리적 귀결입니다.)

그러나 아직까지도 우리는 'R한번 U한번으로 움직이는 경로가 있잖아! 얘는 prime Dyck path아냐? 분해불가잖아!'라고 생각할 수 있습니다.

 2>> 하지만 생각해보면 prime Dyck path란건 시점과 종점을 제외하고 중간에 한번은 닿을 수 있는 점이 있을 때만(= 분해 가능한 경우가 있어야만) 정의가 됩니다.

어떻게 요렇게 조렇게 조합하면 분해할 수 있는 상황에서, 특별한 방법의 조합으로 분해가 불가능한 상황을 정의한 거니까요.

[가령 RURU는 분해가능한 조합이고, 이걸 특별한 방법으로 RRUU로 조합하면 분해가 불가능한 prime Dyck path가 되죠]

그렇다면 너무나도 당연하게 시점과 종점만 있는 상황에서는 prime Dyck path를 정의할 수 없습니다.

[또 다르게 생각해서 1이 소수(prime number)가 아닌 이유와도 상통하겠네요, 1x1에서는 prime Dyck path가 없습니다.]

3>> 다르게 생각하면 하나 작은 격자의 Dyck path를 구함에 있어 그 하나 작은 격자로 '들어가는' 한 스텝과, '나오는' 한 스텝은 필수적으로 필요하기 때문에 카운트 안한다고 생각하셔도 무방합니다.

자, 이제 괄호치기 문제에서 왜 첫번째 괄호를 열고 닫는건 카운트하지 않는지에 대해서 아주 명확하게 해결이 되었습니다.

괄호치기 문제에서의 설명에 더불어 1, 2, 3번 설명 중 와닿는 설명으로 이해하시면 됩니다.

어찌됐든 그래서 첫 카탈란 조합(RU던 ()던)은 노카운트($ C_0 $)입니다!

5] 격자에서의 Dyck path 문제 규칙 살펴보기

요지는 간단합니다.

n x n 격자에서 Dyck path의 경우의 수는 최초 귀환점들로 분해할 수 있습니다.(물론 분해된 모든 경로는 Dyck path일테니 카탈란 규칙을 만족한다는 가정입니다)

따라서 너무나 당연하게도 최초 귀환점들로 분해해서 구한 Dyck path들을 다시 다 더하면 전체 Dyck path의 경우의 수가 될 것입니다.

그리고 최초 귀환점을 기준으로, 최초 귀환점 앞부분은 무조건 prime Dyck path여야 하고(당연히 '최초'귀환이니 y=x에 닿는 지점이 없어야 겠죠?)

그 뒷부분은 그냥 Dyck path이기만 하면 됩니다. 그리고 이 Dyck path를 가지는 경우의 수가 바로 카탈란 수였죠?

그리고 더불어 이렇게 분해를 함으로써 항상 이 분해된 Dyck path의 경우의 수는 전체 경우의 수보다 작아지게 됩니다.

결국 '이전의 수들로 다음 수를 결정한다'는 점화식의 정의를 만족하게 되고, 이 방법론을 따라가면 카탈란 수열의 점화식을 알 수 있게 되겠네요!

바로 n이니 k니 문자를 사용해서 유도를 하면 복잡하고 와닿지도 않게되니, 일단 n=3인 상황을 봅시다.(n=2는 위에서 살펴보았죠?)

아까 prime Dyck path는 y=x-1을 넘지않는 Dyck path의 수라고 했습니다.

그리고 이 말은 항상 최초귀환 점보다 1작은 격자를 Dyck path를 따라 움직이는 것과 마찬가지인 경우의 수를 가지게 됩니다.

이미지로 살펴볼까요?

최초귀환점이 (1, 1)인 경우를 보면 다음과 같습니다.

보시면 아시겠지만, y=x-1선(오렌지색) 아래로 움직일 수 있는 방법이 전혀 없습니다.

이번엔 최초귀환점이 (2, 2)인 경우를 볼까요?

잘 보면 y=x-1보다 아래 즉, (2, 2)보다 1작은 1x1격자(빨간색)에서 Dyck path를 만족하는 경로를 움직이는 것이 prime Dyck path임이 보입니다.

이번엔 마지막 (3, 3)이 최초귀환인 상황을 보죠.

마찬가지로 y=x-1보다 아래 즉, 1작은 (2, 2)격자를 Dyck path로 움직이는 경로가 (3, 3)에서의 prime Dyck path가 됨을 알 수 있습니다.

6] Dyck path 문제로 점화식 구하기

이로써 모든 규칙을 파악했습니다.

4. 마무리

이항정리를 이항급수로 확장하기

📘 카탈란 수열 시리즈

• 🌱 카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?
• 🔢 카탈란 수열의 일반항 구하기: 조합으로 구하기
• 🧮 카탈란 수열의 점화식 구하기
• 📐 카탈란수의 응용: n+2각형에서 삼각형으로 분할하기
• 🧪 카탈란 수열의 일반항을 생성함수로 구해보자 (1)
• 🧰 이항정리를 이항급수로 확장하기
• 🔍 카탈란 수열의 일반항을 생성함수로 구해보자 (2)
• 🔄 라그랑주 역함수 정리 (Lagrange Inversion Theorem)
• 🧠 번외: 카탈란 수를 선형대수로 풀 수 있다고?

1. 이항정리가 뭐야?

이항정리는 중학교 때부터 자연스럽게 접하지만, 제대로 들여다보면 조합, 대수, 함수 등 다양한 수학 영역이 얽혀있는 흥미로운 정리입니다. 간단히 말해서, 어떤 두 항 a와 b의 합을 거듭제곱했을 때, 그 결과를 전개하는 방법을 알려주는 식입니다.

일단 $ (a + b)^2 = (a + b)(a + b) $를 예시로 보면, 2개의 a와 2개의 b중 2개를 고르는 경우의 수라고 볼 수도 있는데요(두개의 괄호에서 각각 a를 (혹은 b를) 고르는 경우의 수죠)

두개의 괄호 모두에서 a를 0개 고르는 경우 b는 무조건 2개 고르는 한가지 경우만 생기고

두개의 괄호 중 한 괄호에서 a를 1개 고르고 다른 괄호에서는 b를 1개 고르는 두가지 경우(ab, ba)가 생기고

두개의 괄호 중 a를 2개 고르는 경우 b는 무조건 0개 고르는 한가지 경우가 생겨서

1, 2, 1이 되죠! 여기서 보면 '두 개 중 0개', '두 개 중 1개', '두 개 중 2개'니까, 각각 $ {_2 C_0}, {_2 C_1}, {_2 C_2} $로 볼 수 있겠네요

그리고 여기서 2는 일반 식에서 n이 되므로 결국 경우의 수는 $ {_n C_0}, ... , {_n C_n} $ 요렇게 되겠군요.

그럼 이 값들은 뭘 뜻하냐고 하냐면, 전개식에서의 계수가 됩니다.

그리고 마찬가지로, 이 경우의 수를 나오게 한 항을 뒤에 붙여서 써주게 되면

$ (a+b)^n = \sum_{k=0}^{n} {_n C_k} a^ka^{n-k} $가 되고,

이를 한번 더 정리해보면 다음과 같이 될 것입니다.

$ (a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k $

(a와 b는 둘 위치가 바뀌어도 상관이 없기 때문에 일부러 위에서와 아래서 지수를 바꿔 써 봤습니다)

여기서 \( \binom{n}{k} \)는 조합(combination) 기호이며, "n개 중 k개를 고르는 경우의 수"를 의미합니다.

이 식이 얼마나 강력하냐면, 단순한 항의 전개뿐 아니라, 파스칼 삼각형, 조합의 성질, 다항식 계수 계산 등에도 응용됩니다. 하지만 이 식은 지금은 정수 \(n\)에 대해서만 정의되어 있죠. 그렇다면 이것을 실수나 더 일반적인 수로 확장할 수 있을까요?

2. 이항정리를 좀 더 정리해보자

우리가 앞으로 확장할 것을 염두에 두고, 이항정리를 조금 더 다듬어 봅시다. 우선, \( a + b \) 대신 \( 1 + x \)로 바꿔 표현해보죠.

그러면 이항정리는 이렇게 됩니다:

$ (1 + x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k $

이제 다항식의 계수가 오직 x에만 의존하게 되며, 함수적 관점에서 다루기 훨씬 쉬워집니다.

3. 정리된 식으로 다르게 구해보자

이번엔 직접 \((1 + x)^n\)을 전개하지 않고, 테일러 급수처럼 항의 계수를 미분을 통해 구해보겠습니다. 실제로 많은 함수들이 이 방식으로 전개되거든요.

우선, 어떤 다항식이 있다고 가정합시다($ (1+x)^n $을 전개하면 계수가 $ a_n $인 다항식이 생성되겠죠?):

$ (1 + x)^n = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n $

여기서 양변에 있는 x에 0을 대입하면, $ a_0 $를 구할 수 있겠죠?

$ 1 = a_0 $입니다.

그리고 위에서 말했듯이 좌우변 모두 x에 대해 미분하면 다음과 같아지겠죠?

$ n(1+x)^{n-1} = 0 + a_1 + 2a_2x + 3a_3x^2 ... $

여기서 x에 0을 대입하면,

$ n = a_1 $이 되겠네요.

하나만 더 해보겠습니다.

한번 더 미분하면

$ n(n-1)(1+x)^{n-2} = 0 + 2a_2 + 3\cdot2 a_3x + ... $

x에 0 대입하면,

$ n(n-1) = 2a_2 $

이제 양변을 계속해서 미분해보면 좌변의 지수가 0으로 떨어지며 우변의 $ a_n $항이 상수항이 되겠죠.

즉, 일반적인 방법으로 구하면 다음과 같은 항이 생깁니다:

$ (1 + x)^n = \sum_{k=0}^{n} \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!} x^k $

여기서 지수가 자연수이므로, 어떤 시점 이후에는 \( n-k+1 = 0 \)이 되어 항이 소멸하게 됩니다. 이것이 다항식이 되는 이유죠. 결국 정리하면:

$ (1 + x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k $

같은 식이지만, 이번에는 다항급수 관점에서 접근한 결과입니다.

4. 지수가 자연수가 아니라면?

그렇다면 이제 지수를 자연수 \(n\)이 아니라, 실수 \(m\)으로 확장해보면 어떻게 될까요?

이제는 위에서 말한 “어느 시점에 0이 되므로 끝나는” 현상이 사라집니다. 다시 말해 무한급수가 되겠죠!

이제 다음과 같은 형태로 일반화할 수 있습니다:

$ (1 + x)^m = \sum_{k=0}^{\infty} \frac{m(m-1)(m-2)\cdots(m-k+1)}{k!} x^k $

즉, 이 식은 더 이상 다항식이 아니라 무한급수, 곧 이항급수가 됩니다.

5. 이항계수를 새로 정의해보자

이제는 이 계수를 일반적인 \( \binom{m}{k} \)로 다시 정의할 수 있습니다. 자연수 \(n\)일 때는 기존 조합 기호를 쓰고, 실수 \(m\)일 때는 다음과 같이 일반화할 수 있죠.

$ \binom{m}{k} = \frac{1}{k!} \prod_{i=1}^{k} (m - i + 1) $

혹은 앞에서 본 것처럼:

$ \binom{m}{k} = \frac{m(m-1)(m-2)\cdots(m-k+1)}{k!} $

이제 이를 이용해서 일반화된 이항급수는 다음과 같이 간단하게 표현됩니다.

$ (1 + x)^m = \sum_{k=0}^{\infty} \binom{m}{k} x^k $

이제 이항정리는 단순한 정수항 다항식을 넘어, 무한급수로 확장된 보편적 전개식이 된 셈입니다.

다시말에 이항정리가 이항급수로 확장된 것이죠!

그리고 물론 이는 자연수에도 적용됩니다.

자연수인경우, k가 m보다 커지는 순간 분자에 무조건 m-m항이 존재하게 되어 그 이후의 모든 식이 0이 되어버리기 때문이죠.

고생하셨습니다!

다음엔 더 재밌는 포스팅으로 돌아올께요!

카탈란 수열의 일반항 구하기: 조합으로 구하기

📘 카탈란 수열 시리즈

• 🌱 카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?
• 🔢 카탈란 수열의 일반항 구하기: 조합으로 구하기
• 🧮 카탈란 수열의 점화식 구하기
• 📐 카탈란수의 응용: n+2각형에서 삼각형으로 분할하기
• 🧪 카탈란 수열의 일반항을 생성함수로 구해보자 (1)
• 🧰 이항정리를 이항급수로 확장하기
• 🔍 카탈란 수열의 일반항을 생성함수로 구해보자 (2)
• 🔄 라그랑주 역함수 정리 (Lagrange Inversion Theorem)
• 🧠 번외: 카탈란 수를 선형대수로 풀 수 있다고?

1. 서론

저번 포스팅에서 살짝 설명했듯이 카탈란 수는 n x n 격자에서 R과 U를 써서, 즉 오른쪽과 위쪽으로 움직이는 방법으로도 찾을 수 있다고 하였습니다.
그렇다면 카탈란 수를 만족하면서 움직이는 방법은 뭘까요?
저번시간 포스팅을 잘 보신 분들이라면 힌트? 아니 답을 바로 아실 수 있을겁니다!

바로 y=x인 선을 넘어가지 않고 움직이는 경우가 바로 카탈란 규칙을 만족하면서 움직이는 방법인데요(Dyck(뒤크) 경로라고도 한답니다)
그렇다면 n x n의 격자에서 카탈란 규칙을 만족하며 움직이는 Dyck 경로의 수만 찾으면 카탈란 수열의 일반항을 바로 구할 수 있겠네요!?
그리고 경우의 수 찾기면 팩토리얼이나 조합(combination)으로 구해지겠군요?

자, 그럼 바로 카탈란수의 일반항을 찾으러 떠납시다!
(참고로 이번 포스팅의 모든 이미지는 제가 직접 만든 것임을 밝힙니다.)
 

2. 카탈란 수의 일반항을 구하기 위한 여정

그러나 안타깝게도 뒤크 경로의 수를 직접적으로 구할 수 있는 방법이 없다는 사실... 물론 어떤 한 점마다 경우의 수를 따져가며 구하려면 구할수야 있겠지만은 수학적으로 간단하게 구하기가 쉽지가 않죠.
그리고 재밌게도 뒤크경로를 만족하는 경우보다 만족하지 않는 경우를 찾는게 더 쉽답니다?
그래서 이제부터 저희는 전체사건에서 뒤크경로를 만족하지 않는 사건을 빼주겠습니다.(확률적으로 여사건이라고 하죠?)
그려면 결국 뒤크경로를 만족하는 경우의 수가 나올테고 이것이 결국 카탈란 수 일테니까요!(그리고 더 나아가 카탈란 수열의 일반항이 되겠죠?)
 
 

2-1. 천릿길도 한걸음 부터: 일단 n x n 격자 이동 총 경로 구하기

이제 뭘 해야 할지 알았으니 바로 작업 들어갑니다.
전체사건은 n x n 격자에서 오른쪽과 위쪽으로 한칸씩 차례대로 이동하여 시점부터 종점까지 움직이는 경우의 수 입니다. 따라서 시점은 좌하단, 종점은 우상단이 되겠네요.
더불어 중복으로 움직이는게 아니라 딱 오른쪽 n번 위쪽 n번만 이동하므로(결국 총 2n번만 움직이게 되는거죠?) 되돌아서 움직이는건 못합니다.
이미지로 나타내보자면 아래와 같겠습니다.

빨간색 점에서 파란색 점까지, 오른쪽 혹은 위쪽으로 한칸씩 이동하며 오른쪽 n번 위쪽 n번 총 2n번 이동하겠군요.
자, 그럼 사실 경우의 수가 다 풀린겁니다.
총 2n번 움직인다고 하였습니다. 결국 2n개를 순서대로 늫어놓는 경우의 수와 마찬가지겠네요. 2n개를 순서대로 늘어놓는 경우의 수는 쉽게 팩토리얼(!)로 구할 수 있죠?
즉, $ 2n! $ 입니다.

그런데 여기서 오른쪽 혹은 위쪽으로 움직이는 것에 순서가 있나요?
가령 오른쪽 명령(R)이 $ R_{(0 \to 1)}, R_{(1 \to 2)}... $ 이렇게 따로 있어서 맨 처음에 오는 오른쪽 명령이 $ R_{(1 \to 2)} $면 시작점에서 갑자기 워프해서 1에서 2로 이동하나요? 아니죠? R은 n개 중에 어떤 R이 와도 무조건 지금 시점부터 오른쪽으로 간다는 의미니까 R끼리는 순서가 의미가 없습니다. 또한 이는 U도 마찬가지겠지요?
그리고 경우의 수에서 '순서가 상관 없어요~'하는 애들은 전체 나열하는 경우의 수에서 그 해당하는 애들끼리 나열하는 경우를 나눠주면 되니까 아까 전체 경우의 수에서 R n개, U n개를 나열하는 경우의 수를 나눠주면 되겠군요! 나열은 팩토리얼!
즉,
$ \frac{2n!}{n!n!} $
으로 나타낼 수 있겠네요!

전체 경우의 수를 아주 쉽게 구했습니다!

(더불어 조합의 정의에 따라 $ _{2n} C_{n} $이라고 표현할 수도 있겠네요. 그리고 개념도 총 2n개의 자리 중 n개의 자리에 R n개를 순서상관없이 채우는 경우라고 볼 수도 있구요.(그러면 자연스럽게 나머지 자리에 U를 다 채우면 경로가 완성이 되겠죠))

자, 그럼 이미지로도 한번 확인해볼까요?
n=2는 너무 간단하니까 n=3으로해서 모든 경로를 그리고, 여기서 카탈란 수 조건에 맞는 경로는 파란색으로, 위반한 경우는 빨간색으로 그려보겠습니다.
 

이미지로 보니까 한눈에 들어오죠!?
3 x 3에서 총 이동경로는 20가지(6!/(3!3!)), 이중에서 카탈란 조건을 만족하며 움직이는 경우의 수는 다섯가지!
 
 

2-2. Dyck 경로가 아닌 경우의 수 구하기

카탈란 조건(차례로 나열하는 어느 순간에도 R>=U)을 만족하는 경로는 다시말해 y = x 직선을 '넘어가지 않는' 경로라고 했습니다.
여기서 딱 봐도 '넘어가지 않는'이란 말이 참 구하기 어려울 것 같지 않나요?

실제로도 이 조건을 위반하는 '위반 타이밍'이 x점마다 있어서 각 경우의 수를 다 고려하지 않으면 안되는 상황이죠.(반대로 생각하려해도 선과 만나는 경우 그리고 만나지 않는 경우를 다 생각해줘야하죠? 복잡합니다..)

그러면 결과는 같은데 조건을 어떻게 바꿔야 우리가 전체 경로의 경우의 수를 구하듯이 쉽게 구할 수 있을까요?

바로 y = x + 1 직선과 만나는 경우를 세면 됩니다!
맞죠? y = x 직선을 '넘어가면, 그 순간 바로 y = x + 1 직선과 만나게 되니까요!
그러면 바로 '위반 타이밍'이 'y = x+1 직선과 만나는 상황' 한가지로 통일되게 됩니다.(이 조건이면 반대로 생각해도 이 선과 만나지 않는 경우로 단 한가지 조건이네요!)

이미지로보면 좀 더 확실하겠죠? 오렌지색 선이 y = x+1, 하늘색 점이 y = x + 1과 만난 점입니다.

그럼 이 경우는 어떻게 셀 수 있을까... 하면 또 기가 막힌 방법이 있습니다.
 
 

2-2-1. 반사원리(Reflextion principle)

자, 지금 조건을 변경해서 조건은 명확해졌지만, 아직도 판 자체가 구하기 어려운 판입니다.
어떻게 보자면 지금 y = x+1 선을 기준으로 ㄱ자를 대칭시켜놓은, ┏ 이런 모양으로 경로가 꺾여있는 것과 마찬가지입니다.
그러면 단순히 펴주면 되겠네요? 어떻게요?
여기서 등장하는 것이 반사원리입니다.
어떤 경로를 가던 처음 y = x + 1선과 만나는 순간, 이 점을 기준으로 지금까지 진행해왔던 경로를 y = x + 1에 대해서 선대칭이동하는 조작을 반사원리라고 합니다.

그렇게 되면 (0, 0)이던 시점은 (-1, 1)로 옮겨지게되죠.

'그러면 문제가 바뀌는거 아니냐!'라고 생각해 볼 수도 있지만, 실제로 처음 만나는 점에서 선대칭이동을하더라도 경우의 수의 차이는 없습니다. 1:1 대응(bijection)이니까요!

자 이미지로 처음 만난 시점부터 대칭을 만들어봤습니다. 아까 하늘 색 점이 위반한 점이라 했는데, 첫 하늘색 점을 기준으로 선대칭이동하였습니다. 보면 실제로 경우의 수는 변화가 없는것을 알 수 있습니다.
 
 

2-2-2. 조금 더 쉽게 개념적으로 설명해보자면...

자, 여기서부터는 제가 더 생각해 본 부분인데요, 반사원리가 조금 생소하다 싶은 분께 개념적으로 어떤 상황인지 설명하기 쉬울 것 같아 만들어본 설명입니다.

이번엔 먼저 이미지부터 보시죠

자 일단 오렌지색 경로를 만나면 무조건 안된다고 했습니다.
그 말인 즉슨, 위에서 보이듯이 빨간 네모를 이동하는 모든 경로는 '안되는' 경로입니다.

자 그럼 이 빨간 경로로 들어가는 방법은 아래 파란박스를 이동하며 들어가는 경로일거고, 나오는 경로는 오른쪽 초록박스를 이동하며 움직일 것입니다.

즉, 여기서 시점부터 파란박스를 이동해서 빨간박스를 이동한 뒤 초록박스를 이동하여 종점으로 가는 모든 경로는 '안되는' 경로 인 것입니다.

자 그럼 간단하게 이 경로를 움직이는 방법만 구하면 되겠네요.
아까말했다시피 굽어져 있는 상태이므로 이를 펴면 쉽게 구할 수 있겠죠.

그리고 펴는 방법은 위에서 알아봤듯 반사원리로 파란박스를 옆으로 이동해서 직사각형을 만들어도 되고, 반대로 초록박스를 위로 이동시켜서 직사각형을 만들어도 경우의 수는 같을겁니다.

여기서 초록박스를 이동하게되면, 위에서 본 반사원리를 거꾸로 적용하여, 가장 마지막에 닿은 점을 기준으로 대칭이동시켜 종점이 대칭이동이 되는 꼴이겠죠.
 
어찌됐든 반사원리든 개념적인 설명이든 이 방법을 사용하면 아주 간단하게 '안되는' 경우의 수를 찾을 수 있습니다.


최종적으로 안되는 경우의 수는 $ \frac{2n!}{(n+1)!(n-1)!} $ 이겠네요!
[(-1,-1) 부터 (n, n)(여기서는 (3, 3))까지 움직이는 경로는 가로로 n+1번 세로로 n-1번, 전체 2n번 움직이는 경로일테니까요]
 
 

2-3. 뒤크 경로를 만족하며 움직이는 경로의 경우의 수

다 구했습니다.

이제 전체 경우의 수에서 뒤크경로를 만족하지 않는 경우의 수를 빼 주면 뒤크경로를 만족하는 경우의 수가 나오게 됩니다.
즉,

$ C_n = \frac{2n!}{n!n!} - \frac{2n!}{(n+1)!(n-1)!} $
 
 

3. 결론

네, 이미 구했다시피 카탈란 수의 일반항은 바로

$ C_n = \frac{2n!}{n!n!} - \frac{2n!}{(n+1)!(n-1)!} $
이 됩니다!
 
그리고 잘 보면 조금 더 정리할 수 있을 것 같지 않나요?
일단 공통된 부분을 묶어보면,
$ C_n = \frac{2n!}{n!(n-1)!} \left(\frac{1}{n} - \frac{1}{n+1}\right) $
통분하여 정리하면
$ C_n = \frac{2n!}{n!(n-1)!} \left(\frac{1}{n(n+1)}\right) $
다시 합치면
$ C_n = \frac{2n!}{(n+1)!n!} $
짠! 깔끔하게 정리된 일반항을 얻었습니다!

조합으로 써보자면

$ C_n = \frac{1}{n+1}{_{2n}C_{n}} = \frac{1}{n+1}\binom{2n}{n} $
이렇게 되겠네요!

이렇게 카탈란 수의 일반항을 조합적인 방법을 이용하여 구했습니다!
 
 

4. 응용

지금까지 배운 것을 응용해서 n=4와 n=5인 경우도 구해볼까요?
여기서는 깔끔하게 유도된 최종 형태 말고, 우리가 실제로 구했던 방법대로 구해볼께요!
n = 4일 때 전체 경로의 수는
$ \frac{8!}{4!4!} = 70 $
카탈란 수는
$ C_4 = \frac{8!}{4!4!} - \frac{8!}{5!3!} = 70 - 56 = 14$
실제 이미지로 만들어보면

정확히 맞죠?
 
n = 5일 때 전체 경로의 수는
$ \frac{10!}{5!5!} = 252 $
카탈란 수는
$ C_4 = \frac{10!}{5!5!} - \frac{10!}{6!4!} = 252 - 210 = 42 $
얘도 그려보면,

맞는게 딱 보이네요!
 
n=6 부터는 계산해봐도 전체 경로 924, $ C_5 = 132 $이므로 더이상은 그리기 힘... 듭니다만은 그려봅시다

여튼, n=3으로 구했지만, 결국 n에 대하여 전부 성립하는 일반항을 구했습니다!
 

5. 미리니름

자, 다음번에는 카탈란수의 점화식을 한번 유도해보도록 하겠습니다!

카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?

📘 카탈란 수열 시리즈

• 🌱 카탈란(Catalan) 수열 - 카탈란 수열이란게 뭔데?
• 🔢 카탈란 수열의 일반항 구하기: 조합으로 구하기
• 🧮 카탈란 수열의 점화식 구하기
• 📐 카탈란수의 응용: n+2각형에서 삼각형으로 분할하기
• 🧪 카탈란 수열의 일반항을 생성함수로 구해보자 (1)
• 🧰 이항정리를 이항급수로 확장하기
• 🔍 카탈란 수열의 일반항을 생성함수로 구해보자 (2)
• 🔄 라그랑주 역함수 정리 (Lagrange Inversion Theorem)
• 🧠 번외: 카탈란 수를 선형대수로 풀 수 있다고?

오랜만의 포스팅으로 돌아왔습니다.
 
요 근래 새롭게 관심이 생긴 수열이 있습니다.
바로 카탈란 수열(Catalan Number)입니다. 뭐 카탈랑 수열이라고도 한다는군요.
어찌됐든, 그럼 이 수열은 어떻게 정의가 되는가... 하면, 일단 한가지 이야기를 해보도록하겠습니다.

카탈란 수열을 처음부터 파헤쳐 보자!

1. 카탈란 수열이 뭐길래?

카탈란 수열은 외젠 샤를 카탈랑(Eugène Charles Catalan)이 1838년에 제안하였습니다.

1-1. 카탈란 수열의 정의

카탈란 수열의 정의는 다음과 같습니다.

각 n개씩 가지고 있는 두 종류의 기호(A, B)를 길이 2n으로 나열할 때, 나열하는 매 순간 A의 개수가 B의 개수보다 적지 않도록 배열하는 방법의 수(나열하는 매 순간 $ \sum A \ge \sum B $)

또는

'1(A)' n개와 '-1(B)' n개를 2n개까지 차례대로 나열할 때, 나열하는 매 순간까지의 부분합이 음수가 되지 않게 나열하는 경우의 수
그 값이 바로 카탈란 수 $C_n$입니다.

그리고 여기서 각 n에 해당하는 경우의 수를 카탈란 수(Catalan Number), 이 수들이 이루는 수열을 카탈란 수열(Catalan Series)라고 합니다.

2. 예시 살펴보기

2‑1. 영화관 잔돈 문제

어느 영화관 주인은 잔돈 0원으로 영업을 시작하고 마감까지 잔돈이 생기면 안 됩니다. 영화표는 5,000원, 손님은 5,000원권(A)과 10,000원권(B)만 가지고 오죠. 줄 세우는 순간순간 A ≥ B를 만족해야 잔돈을 거슬러 줄 수 있습니다. 총 $2n$명의 손님(A $n$명, B $n$명)이 들어올 때 가능한 줄 세우기 가짓수가 $C_n$!

2‑2. 올바른 괄호 문자열

프로그래머라면 익숙한 “괄호 짝 맞추기” 역시 카탈란 수의 고전 예시입니다. 길이가 $2n$인 문자열에서 (를 A, )를 B라 두고 어느 접두사(미완성 문자열)에서도 ( 개수 ≥ ) 개수, 최종적으로 동일한 개수를 만족해야 “올바른 괄호”가 됩니다. 그 가짓수가 또 $C_n$!

2‑3. 뒤크(Dyck) 문자열

문자열 이론에서는 이런 문자열을 Dyck 문자열이라 부릅니다. 조건은 동일해요.

• 길이 $2n$
• A와 B가 $n$개씩
• 모든 접두사(미완성 문자열)에서 A ≥ B

영화관, 괄호치기, Dyck 문자열… 전부 같은 문제를 다른 언어로 설명했을 뿐이라는 사실!

2‑4. 볼록 다각형 삼각 분할(대각선 갯수 예시)

• 모든 n각형의 내각의 합은 180°(n-2)입니다.
• 그 이유는 n각형은 항상 n-2개의 삼각형으로 분할할 수 있으며, 삼각형의 내각은 항상 180°이기 때문이죠.
• 여기서 볼록 다각형(n+2각형)을 삼각분할 하는 경우의 수(대각선 개수)는 꼭지점 고정시 재귀적으로 하위 다각형을 만들어가는 구조이며, 카탈란 수로 귀결됩니다!
• 단순 나열의 문제가 아닌 도형과 결부되며, 재귀적인 조합이 들어가는 문제이므로 자세한 유도는 이후 따로 진행하도록 하겠습니다.

즉, “교차하지 않는 대각선으로 삼각 분할” 이라는 조건이 A ≥ B 조건과 같은 재귀 구조를 만들어 낸다는 사실! 도형에서도 카탈란 수가 튀어나오는 이유가 여기 있습니다.

좀 더 확장해서 원 위에서 2n개의 점을 잡고 교차하지 않는 n개의 선분을 긋는 경우의 수도 포함됩니다!

2-5. n개의 노드를 가지는 이진트리 구성 방법의 수

• 이진트리는 노드 하나 + 왼쪽, 오른쪽 두개의 리프(leaf)노드를 가질 수 있는 구조입니다.
• 보통 첫 시작 노드는 루트 노드(root node), 말단 노드를 리프 노드(leaf node), 그 외 노드들을 내부 노드(internal node)라고 부릅니다.
• 여기서 n개의 노드를 가지는 이진트리를 구성하는 방법의 수가 카탈란 수!

2-6. 스택정렬 가능한 방법의 수

스택(stack)이란 바구니죠 바구니.

이 바구니에 어떤 숫자를 차례대로 넣을 때 만들 수 있는 경우의 수가 또한 카탈란 수 입니다.

가령 1, 2, 3이라고 하는 수를 차례대로 바구니에 넣을 때

1 넣고 바로 빼고 2 넣고 바로 빼고 3 넣고 바로 빼면 => 123

1 녛고 바로 빼고 2 넣고 3넣고나서 3빼고 2빼면(바구니라 넣었던 순서의 반대로밖에 못꺼냅니다) => 132

1 넣고 2넣고 바로 빼고 3 넣고 바로 빼고 마지막 1 빼면 => 231

1 넣고 2넣고 바로 빼고 1빼고 3넣고 바로 빼면 => 213

1 넣고 2 넣고 3 넣은 다음, 3빼고 2빼고 1빼면 => 321

이 다섯가지 경우밖에 만들 수 없고, 이것이 바로 $ C_3 $에 해당하는 5죠!

결국 정리해보면,

• 스택(stack)이란 바구니이며, 이 바구니에 특정 n가지의 수를 넣었다 빼었을 때 나올 수 있는 숫자(스택 정렬 가능한 숫자)
• ‘넣는 행위(push)’와 ‘빼는 행위(pop)’을 A와 B에 대응시키면 정확하게 카탈란수를 따른다.

라고 볼 수 있습니다!

3. n × n 격자 맛보기

3‑1. R은 오른쪽, U는 위쪽

A를 R(오른쪽), B를 U(위쪽)으로 바꿔 생각해 봅시다. 그럼 (0,0)에서 (n,n)까지 오른쪽·위쪽으로만 2n번 이동하는 경로가 생깁니다. 조건 A ≥ B는 언제나 $y≤x$ 선 아래에 있다는 뜻. 이 경로를 Dyck 경로라고 부르는데, 본격적인 분석은 다음 포스팅에서 진행할 예정이니 여기서는 “카탈란 수가 격자 경로와도 연결된다!”만 기억해 두면 OK.

4. 작은 n 직접 세어 보기

$n$이 커질수록 폭발적으로 늘어나죠? 실제로 카탈란 수열은 다음과 같습니다. $$ 1,\;1,\;2,\;5,\;14,\;42,\;132,\dots $$

5. 왜 재미있을까?

• 영화관 잔돈 같은 스토리텔링 예제
• 괄호치기·컴퓨터 스택 문제
• 다각형 삼각 분할·트리 구조 등 수학·CS 곳곳에서 등장

이렇게 많은 분야에 얼굴을 내미니 안 재밌을 수가 없죠!

6. 마무리

오늘은 “카탈란 수는 무엇인가?”를 중점적으로 살펴봤습니다. 다음 포스팅에서는 다음 포스팅에서는 일반항 $C_n$을 손에 넣는 과정을 차근차근 풀어 보겠습니다. 기대해 주세요!

마비노기 모바일 PC버전 다운로드 안될 때

마비노기 모바일이 아주 요새 핫하다해서 모바일로 즐기던 중 아무래도 PC가 하기 편하지 않을까 싶어 PC버전을 다운로드 받으려는데!

홈페이지에서 첫 페이지에서 'GAME START'버튼이 안뜨고, 심지어 다운로드 페이지에 들어가도 '다운로드' 링크가 안뜬다면!!

해상도의 문제일 수 있습니다.

마비노기 모바일 홈페이지가 진짜 왜 그렇게 만들었는진 모르겠는데 반응형 웹사이트로 이 버튼이 뜨게/안뜨게 해놨더라구요.

간단하게, 브라우저에서 '확대/축소'하셔서 화면을 조금 축소해주면 바로 버튼들이 나타납니다!!

키보드에서 'ctrl'누르고 마우스 휠 돌리셔도 같은효과입니다!

저같이 며칠동안 PC버전 시작도 못해보시는 일 없기를 바랍니다...