번외: 카탈란 수를 선형대수로 풀 수 있다고?
📘 카탈란 수열 시리즈
- 🌱 카탈란(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. 한 칸만 이동하므로 대각선 근처에만 값이 있는 희소행렬 구조
위에서 전이행렬을 정의할 때를 잘 보면(즉 무조건 한번 이동한다고 하면)
- 자기 자신으로 움직일 수는 없다
- 한 번에 두 칸 이상 움직일 수는 없다(무조건 한 칸만 이동해야 한다)
의 두가지 조건에 의해 그렇게 움직일 수 있는 경우는 전부 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. 총평
이처럼 카탈란 수는 조합적 정의, 생성함수, 역함수 정리뿐 아니라, 선형대수의 관점에서도 풀어낼 수 있는 문제입니다.
이 방식은 일반항 도출에는 적합하지 않지만, 구조적 이해와 계산 방법, 알고리즘 구현에서 강점을 지니고 있습니다.(특히나 덧셈의 반복계산은 코딩문제에 아주 적합하죠)
정말 이것으로 찐 카탈란 수 시리즈를 마무리 짓겠습니다!
따라오시느라 수고 많으셨습니다!
'Study > Mathematics' 카테고리의 다른 글
라그랑주 역함수 정리(Lagrange Inversion Theorem) (0) | 2025.05.22 |
---|---|
카탈란 수열의 일반항을 생성함수로 구해보자(2) (0) | 2025.05.20 |
카탈란 수열의 일반항을 생성함수로 구해보자(1) (0) | 2025.05.19 |
카탈란수의 응용: n+2각형에서 삼각형으로 분할하기 (0) | 2025.05.17 |
카탈란 수열의 점화식 구하기 (0) | 2025.05.12 |