카탈란 수열의 일반항을 생성함수로 구해보자(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 $이라는 수열 전체의 정보를 담고 있는 생성함수인 것입니다!


여기까지 읽으셨는데도 생성함수에 대해서 감이 잘 오지 않으신다면 생성함수(Generating Function)란?(feat. 멱급수(power series)) 포스팅을 한번 보시면 더욱 쉽게 이해가 가실겁니다!

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. 조금 더 쉽게 개념적으로 설명해보자면...

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

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

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

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

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

다시말해 이 말은 절대 움직이면 안되는 경로인 빨간 박스 영역과 그 영역으로 들어가는 경로인 파란박스 그리고 나오는 경로인 초록박스, 바로 이 세 영역이 빨간박스의 네 변중 두 변에 붙어있기만 하면 어떤 모양을 하던지 상관이 없다는 의미가 됩니다. 

단적인 예로 네가지 정도만 뽑아봤습니다.

이와같이 다향한 모양으로 변형시켜도 그 경우의 수는 모두 같을 수 밖에 없습니다. 특히 몇가지 경우는 돌리거나 대칭이동시키기만해도 나오는 모양이므로 직관적으로 이해가 쉽죠?

그래서 우리는 이 모양들 중 가장 계산하기가 편한 1번 모양을 쓰는겁니다. 그리고 이 모양이 위에서 '반사원리'라고 하는 원리가 적용된 모양과 동일한 모양이죠.(제일 처음 이미지의 파란박스를, 1번 모양과 비교해보면 y=x+1에 대해서 선대칭(반사)인 것을 알 수 있습니다.)

여담으로 반대로 마지막에 닿은 점을 반전시켜 종점을 대칭시킨 반사원리를 이용할 수도 있습니다. 이 모양은 네번째 모양이 되는거구요.(이것도 처음 이미지와 비교해보면 초록박스가 y=x+1에 대해서 선대칭(반사)입니다.)

자 그럼 간단하게 이 경로를 움직이는 방법만 구하면 되겠네요.
위에서 말했다시피 굽어져 있는 상태이므로 이를 편 모양으로 만들면 쉽게 구할 수 있겠죠.

그리고 펴는 방법은 위에서 알아봤듯 반사원리로 파란박스를 옆으로 이동해서 직사각형을 만들어도 되고, 반대로 초록박스를 위로 이동시켜서 직사각형을 만들어도 경우의 수는 같을겁니다.(결국 첫번째 모양이나 네번째 모양으로 만든다는 뜻입니다.)
 
어찌됐든 반사원리든 개념적인 설명이든 이 방법을 사용하면 아주 간단하게 '안되는' 경우의 수를 찾을 수 있습니다.


최종적으로 지금까지 알아본, '변형시킨 격자'를 이동하는 경로는 안되는 경우의 수가 됩니다.

따라서 (-1,1) 부터 (n, n)(여기서는 (3, 3))까지 움직이는 경로는 가로로 n+1번 세로로 n-1번, 전체 2n번 움직이는 경로의 경우의 수를 구하면 되겠네요.

그렇다면 그 경우의 수는 $ \frac{2n!}{(n+1)!(n-1)!} $ 이 되겠습니다.
 
 

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$을 손에 넣는 과정을 차근차근 풀어 보겠습니다. 기대해 주세요!

피보나치 수열을 선형대수로 풀어보자

 
피보나치 수열 해체에 멱급수가 끝인 줄 알았건만... 또 새로운 insight로 선형대수로도 풀어볼 수 있게 됐네요..
1. 계차의 등비수열로 풀기
2. 특성방정식으로 풀기
3. 멱급수로 풀기
 
 

1. 선형대수로 풀 수 있다고?

우리는 이미 앞에서 피보나치 수열의 일반항도 구했고, 여러 방법으로 구해보기도 하였습니다.
이 과정을 선형대수로도 할 수 있다는 것이 이 포스팅의 골자가 되겠네요.
 
 

2. 어떻게 풀건데?

2-1. 피보나치 수열을 선형대수적으로 나타내기

일단 수열 $ F_n $을 선형대수적으로 정의해봅시다.
$ F_n = F_{n-1} + F_{n-2} $를
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \underbrace{\begin{bmatrix} 1&1\\1&0 \end{bmatrix}}_{\mathsf{Companion \; Matrix}} \begin{bmatrix} F_{n-1}\\F_{n-2} \end{bmatrix} $
이렇게 표현 가능합니다. 여기서 잘 보면 $ F_n $과 $ F_{n-1} $ 사이에 생기는 행렬을 Companion matrix(동반 행렬)이라고 하는데, 어떻게 저렇게 표현되는지는 사실 간단합니다.
일단 그냥 $ F_n $을 $ F_n $과 $ F_{n-1} $을 성분으로 갖는 열벡터로 정의합시다.(선형대수에서 벡터의 의미는 열이나 행 하나로 정의된 행렬을 뜻합니다)
$ \overrightarrow{F_n} = \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} $
이 될 것이고, 여기서 $ F_n = F_{n-1} + F_{n-2} $라는 피보나치 수열의 정의를 이용하면
$ \overrightarrow{F_n} = \begin{bmatrix} F_{n-1}+F_{n-2}\\F_{n-1} \end{bmatrix} $
덧셈의 항등원인 0까지 넣어주면
$ \overrightarrow{F_n} = \begin{bmatrix} F_{n-1}+F_{n-2}\\F_{n-1}+0 \end{bmatrix} $
좀 더 보기 편하게 곱셈의 항등원 1도 표시해주죠
$ \overrightarrow{F_n} = \begin{bmatrix} 1 \cdot F_{n-1}+1 \cdot F_{n-2}\\ 1 \cdot F_{n-1}+ 0 \cdot F_{n-2} \end{bmatrix} $
행렬의 곱셈공식을 생각해서 분리해보면
$ \overrightarrow{F_n} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \begin{bmatrix} F_{n-1}\\F_{n-2} \end{bmatrix} $
여기서
$ \overrightarrow{F_n} = \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} $
이므로
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \begin{bmatrix} F_{n-1}\\F_{n-2} \end{bmatrix} $
이렇게 유도가 됩니다. 그리고 이를 벡터로 표기하면
$ \overrightarrow{F_n} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \overrightarrow{F_{n-1}} $
이렇게도 표현할 수 있겠죠?
 

2-2. 피보나치 수열을 변환하기

자, 그럼 아주 재밌게도 $ F_n $과 $ F_{n-1} $ 사이에는 companion matrix의 곱만큼 차이가 납니다.
가령, $ F_{n-1} $을 표현해보아도
$ \overrightarrow{F_{n-1}} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \overrightarrow{F_{n-2}} $
일 것이고, 이를 위 식에 대입을 하면
$ \overrightarrow{F_n} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \overrightarrow{F_{n-1}} $
$ \overrightarrow{F_{n-1}} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \overrightarrow{F_{n-2}} $
$ \overrightarrow{F_n} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix} \overrightarrow{F_{n-2}} $
$ \overrightarrow{F_n} = \begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix}^2 \cdot \overrightarrow{F_{n-2}} $
가 되겠고, 이제 조금 표기의 편의성을 위해 companion matrix를 A라고 놓으면
$ \overrightarrow{F_n} = A^2 \cdot \overrightarrow{F_{n-2}} $
라고 표기할 수 있겠습니다. 자, 다시 돌아가서 $ F_n $과 $ F_{n-1} $ 사이에는 companion matrix의 곱만큼 차이가 난다고 했습니다.
그렇다면 이를 이용하면 $ F_n $을 $ F_{1} $으로 표현도 가능하겠네요?
그렇다면 companion matrix A는 n-1번 곱해지면 되겠습니다.
$ \overrightarrow{F_n} = A^{n-1} \cdot \overrightarrow{F_{1}} $
열벡터를 풀어서 행렬로 보게 된다면
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = A^{n-1} \cdot \begin{bmatrix} F_{1}\\F_{0} \end{bmatrix} $
여기서 $ F_1 = 1, \; F_0 = 0 $이므로,
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = A^{n-1} \cdot \begin{bmatrix} 1\\0 \end{bmatrix} $
이렇게 깔끔하게 정리가 되겠네요!
여기까지는 아주 순조롭습니다! 여기까지는...
 
자, 여기서 어려움에 봉착합니다.
행렬의 곱은 일반 적인 대수적 곱이랑은 다르다고 했습니다.
그렇다면 곱으로 연결되어있는 행렬, 즉 행렬의 거듭제곱은 쉬울까요? 각 요소에다가 각자 다 거듭제곱을 붙여주면 되는걸까요?
아뇨.. 일반적으로는 매우 어렵습니다. 대수의 거듭제곱처럼 쉬웠으면 얼마나 좋을까요..
그렇다고 거듭제곱으로 압축표기된 행렬을 쫙 풀어놓고 하나하나 곱하고 있자니 그것도 조금 메롱합니다..
물론 앞의 몇번을 반복하고 수학적 귀납법으로 이런 규칙이 있다!하고 찾은 뒤 적용해주어도 괜찮지만, 우리는 뭔가 좀 더 신박한 방법을 찾아보려 합니다.
그렇다면 행렬을 일반 대수처럼, '행렬의 거듭제곱 = 요소의 거듭제곱'으로 나타낼 수 있는 행렬이 있을까요?
 
예, 행렬의 곱셈에 대해 조금만 생각해보면, '대각행렬'은 자기 자신이 속한 행과 열 중에서 자기 자신을 제외한 다른 요소들이 전부 0이므로 행렬의 곱셈을 수행하여도 자기 자신의 거듭제곱만 결과로 나타나게 됩니다! 즉,
$ \begin{bmatrix} 1&0\\0&2 \end{bmatrix}^2 = \begin{bmatrix} 1&0\\0&2 \end{bmatrix}\begin{bmatrix} 1&0\\0&2 \end{bmatrix} = \begin{bmatrix} 1&0\\0&4 \end{bmatrix} = \begin{bmatrix} 1^2&0\\0&2^2 \end{bmatrix} $
오! 결국 행렬의 거듭제곱을 요소의 거듭제곱으로 표현할 수 있는 방법을 찾았습니다!
그럼 행렬을 대각행렬로 바꿔주면 되겠네요!? 근데.. 어떻게 해야하죠...?
 
여기서 나오는 개념이 바로 '대각화'입니다.
연역적으로 너무나도 당연하게 한 행렬을 대각행렬로 바꿔주는 작업이죠.
그런데, 딱 봐도 뭔가 그럴싸해보이는 작업이 맨입으로 가능할까요? 아니겠죠...
그래서 대각화에 앞서서 바로 '고유값 분해(eigen decomposition)'가 필요합니다.
갑자기 뭔가 난이도가 엄청 뛴 느낌입니다.
 

2-3. 대각화를 위한 고유값 분해

간단하게 고유값 분해를 설명하자면, '어떤 행렬을 어떤 벡터에 곱한 값이 그 어떤 벡터의 상수배 만큼과 같은 그 어떤 벡터와 상수 찾기'라고 생각하시면 됩니다.
좀 더 설명해보자면, 행렬의 곱은 기본적으로 어떤 공간에서의 좌표변환 역할을 합니다.
그러나 이 행렬의 변환을 거쳐도 변하지 않는 그런 벡터를 찾는 것이 고유벡터(아이젠 벡터, eigen vector)를 찾는 과정입니다.
그리고 물론 이 벡터는 변환을 거쳐서 특정 상수배만큼 길이가 길어지거나 짧아질텐데, 바로 그런 상수를 찾는 것이 고유값(아이젠 벨류, eigen value)을 찾는 과정입니다.
그리고 이둘이 한번에 이루어지기때문에 고유값분해라고 명명지어진 것이죠.
그럼 실제로 한번 어떻게 이루어지는지 봐 볼까요?
아, 참고로 고유값 분해는 정방행렬에서만 적용된답니다. 이를 확장한게 특이값 분해(singular value decomposition)죠.
 
자, 일단 '어떤 행렬과 곱한 열벡터' 즉, '행렬변환을 한 열벡터'라는 식을 세워봅시다.
지금 쓰는 A 행렬은 위에서의 companion matrix였던 A행렬과 다른 행렬입니다.
$ A \cdot \overrightarrow{v} $
그리고, '상수배만큼 변한 열벡터'도 식으로 세워보죠
$ \lambda \cdot \overrightarrow{v} $
이젠 이 둘을 합쳐 동치로 놓습니다. 뜻은 아까 말했듯 'A 행렬 변환을 거친 벡터 = 특정 상수배 만큼 변한 벡터'입니다. 결국 벡터의 방향은 바뀌지 않고 크기만 바뀐셈이죠
$ A \cdot \overrightarrow{v} = \lambda \cdot \overrightarrow{v} $
그리고 이걸 풀기위해 이항하여 =0으로 바꿔줍니다.
$ A \cdot \overrightarrow{v} - \lambda \cdot \overrightarrow{v} = 0 $
공통된 벡터를 묶어줍니다. 행렬에서는 곱하는 방향이 중요하기 때분에(교환법칙 성립 x) 같은 방향으로 묶어줍니다.
$ (A - \lambda) \overrightarrow{v} = 0 $
근데 여기서 문제가 생깁니다. A는 행렬이고, $ \lambda $는 스칼라거든요..
그럼 어떻게 처리해줘야할까요? 행렬을 스칼라로? 스칼라를 행렬로?
 
네, 스칼라 값을 행렬로 변환해줘야합니다.
왜냐하면 지금 저희는 어떤 변환을 하더라도 변하지 않는 벡터를 찾는 중이니까요, 어떤 변환을 하는 행렬을 찾아야죠
그러면 $ \lambda $를 어떻게 행렬로 변환 할 것이냐...
일단 행렬의 뺄셈을 하려면 행렬의 크기가 맞아야겠죠?
그럼 이 스칼라 값에 어떤 행렬을 곱해주면 될텐데.. 어떤 행렬을 곱해줄까요..? 그냥 A행렬과 크기만 맞는 행렬이면 다 되는 걸까요?
 
물론 아니겠죠..! 스칼라 값을 어떤 행렬 공간에서 동일하게 작용하는 행렬로 확장하려면 단위행렬을 곱해줘야 합니다.
좀 더 정확하게 말하자면 [단위행렬은 '모든 벡터를 자기 자신으로 보존'하는 유일한 선형변환]이기 때문입니다.
어떻게 보자면 곱셈의 항등원과 같은 뜻입니다.
자, 이렇게 알아냈으니 다시 식을 써보죠
$ (A - \lambda \cdot I) \overrightarrow{v} = 0 $
네, 이게 바로 고유값 분해의 식입니다.
 
그리고 여기서 잘 보자면, 결국 $ (A - \lambda \cdot I) $가 0이거나, $ \overrightarrow{v} $가 0이어야지만이 이 식이 성립함을 알 수 있습니다.
그런데, 저희는 처음 시작부터 고유 벡터 $ \overrightarrow{v} $가 있다! 하고 가정을 하고 출발했으니까 $ \overrightarrow{v} $는 0이 되면 안됩니다. 결국, $ (A - \lambda \cdot I) $가 0이 되어야 하는데... 이게 0이 되는걸 어떻게 찾을 수 있을까요?
행렬을 단 하나의 스칼라 값으로 바꾸는 방법은 여러가지가 있지만, 그 중에서도 행렬식(determinant)이 가장 대표적입니다.
 

그냥 간단하게 스칼라 값으로 바꾼다고 했지만, 사실 고등학교정도의 행렬을 배웠던 사람이라면 행렬식은 좀 익숙할 겁니다.
바로 역행렬을 만들때 필요한 친구이기 때문인데요, 고등학교에서는 역행렬을 만들 때, $ \begin{pmatrix} a&b\\c&d \end{pmatrix}^{-1} = \frac{1}{ad-bc} \begin{pmatrix} d&-b\\-c&a \end{pmatrix} $로 배웠을 거에요.
그리고 사실 $ ad-bc $가 행렬식(determinant)이죠.
그리고 여기서 '행렬식이 0이면, 역행렬이 없다' = '역행렬이 존재하려면 행렬식이 0이면 안된다'는 결론이 나옵니다.
결국 이 문제에서도 $ (A - \lambda \cdot I) $가 역행렬이 있으면 안되기 때문에 $ det(A - \lambda \cdot I) $(행렬식 연산을 det라고 줄여서 표기합니다)가 0인 것을 찾는 겁니다.
여담으로 $ (A - \lambda \cdot I) $가 역행렬이 된다면,
$ (A - \lambda \cdot I)^{-1} (A - \lambda \cdot I) \overrightarrow{v} = (A - \lambda \cdot I)^{-1} \cdot 0 $
$ \overrightarrow{v} = 0 $
즉, 고유벡터가 영벡터가 되어버리므로 결국 저희가 세웠던 가정이 맞지 않게되어버립니다.

 
행렬식은 이미 아시다시피 2차는 아주 간단하게 $ \begin{pmatrix} a&b\\c&d \end{pmatrix} $ 행렬에서 $ ad-bc $입니다.
3차부터 복잡해지지만, 일단 저희는 지금 피보나치 수열을 구하는 수준에서 2차까지 알아보겠습니다.
 
자 그럼 다시 돌아와서, 우리는 지금 companion matrix를 대각화 하고 싶고, 그래서 방법을 찾다보니 우선 고유값 분해를 해야한다는 걸 알았습니다.
그러면 companion matrix를 고유값 분해합시다.
$ (A - \lambda \cdot I) \overrightarrow{v} = 0 $
여기서 A는 현재 companion matrix의 A입니다.
$ det(A - \lambda \cdot I) = 0 $이면 된다고 했습니다.
일단, 실제값으로 바꿔보죠
$ det( \begin{bmatrix} 1&1\\1&0 \end{bmatrix} - \lambda \cdot \begin{bmatrix} 1&0\\0&1 \end{bmatrix} ) = 0$
$ det( \begin{bmatrix} 1&1\\1&0 \end{bmatrix} - \begin{bmatrix} \lambda&0\\0&\lambda \end{bmatrix} ) =0 $
$ det( \begin{bmatrix} 1-\lambda&1\\1&-\lambda \end{bmatrix} ) =0 $
 
여기서 행렬식 연산을 해줍니다. $ ad-bc $
$ (1-\lambda)(-\lambda)-1 = 0 $
$ \lambda^2 - \lambda -1 = 0 $
풀어주면 되겠죠? 근의 공식에 넣어서 풀어주면 됩니다. 여기까지 오면서 정말 많이 풀었으니까(다른 포스팅에서 피보나치 수열 풀던 가락..) 여기서는 그냥 바로 뿅 가겠습니다.
$ \lambda = \frac{1+\sqrt5}{2} \; or \; \frac{1-\sqrt5}{2} $
$ \lambda_1 = \frac{1+\sqrt5}{2}, \; \lambda_2 = \frac{1-\sqrt5}{2} $
이렇게 놓을 수 있겠네요!
고유값(eigen value) 찾았습니다!
 
그럼이제 고유벡터를 찾아야겠죠?
고유벡터의 요소를 ab라고 놓으면,
$ \overrightarrow{v} = \begin{bmatrix} a\\b \end{bmatrix} $
$ \lambda $값이 두개였으니까 하나만 살펴보죠
$ (A - \lambda_1 \cdot I) \overrightarrow{v_1} = 0 $ 이므로,
$ \begin{bmatrix} 1-\lambda_1&1\\1&-\lambda_1 \end{bmatrix} \begin{bmatrix} a\\b \end{bmatrix} = 0 $ 이겠네요.
풀면,
$ \begin{cases} (1-\lambda_1)a+b = 0 \\ a-\lambda_1 b = 0 \end{cases} $
결국, $ a = \lambda_1 b $이고
$ \overrightarrow{v_1} = \begin{bmatrix} \lambda_1 b\\b \end{bmatrix} $
여기서 고유벡터는 방향만 나타내주면 되는 성분이니 그냥 가장 간단하게 b에다가 1 대입하면
$ \overrightarrow{v_1} = \begin{bmatrix} \lambda_1 \\1 \end{bmatrix} $
요렇게 정리가 됩니다. $ \lambda_2 $에 대해서 정리해도 똑같죠!
고유벡터(eigen vector) 찾았습니다!

위에서 왜 연립방정식 안푸냐... 하시는 분들도 계실텐데.. 두번째 식 $ a = \lambda_1 b $을 첫번째 식에 대입해서 풀어보시면 그냥 의미없이 $ b \cdot 0 = 0 $이런 결과를 얻으실 겁니다...

 
자, 그리고 이제 이 고유벡터를 column으로 stack한 새로운 행렬 P를 정의해보죠.(열벡터를 쌓아서 행렬 만들기는 흔한 조작중에 하나입니다)
$ P = \begin{bmatrix} v_1&v_2 \end{bmatrix} = \begin{bmatrix} \lambda_1&\lambda_2\\1&1 \end{bmatrix} $
자, 이제 대각화를 할 준비를 마쳤습니다.
어휴.. 쓰다보니까 진짜 엄청 기네요! 잘 따라와주세요!(사실 보통은 따로따로 파편적으로 공부하지만 이렇게 한번에 쭉 보는것도 도움이 된답니다!)
 

2-4. 드디어 대각화

자, 우리의 염원이던 '행렬의 거듭제곱 = 요소의 거듭제곱 그러나 답은 바뀌지 않는'을 찾기위한 여정의 막바지 입니다.
일단 우리는 companion matrix인 A를 알고있고, 고유벡터를 쌓아서 만든 P라는 matrix를 알고있습니다.
일단 이 두개. 곱해보죠.
$ AP = A \begin{bmatrix} v_1 & v_2 \end{bmatrix} $
자, 혹시 여기서 설명이 조금 헛갈리시면 행렬곱셈 개념정리를 한번 참조해주시기 바랍니다.
matrix와 column끼리 곱한 column을 모아도 행렬의 곱셈이 성립한다고 했습니다.
그렇다면 여기서 이렇게 식을 변형할 수 있겠네요?
$ AP = \begin{bmatrix} A \cdot v_1 & A \cdot v_2 \end{bmatrix} $
근데 위에서 우리는 고유값 분해를 했습니다.
고유값 분해식은
$ A \cdot \overrightarrow{v} = \lambda \cdot \overrightarrow{v} $
이거였죠.
어? 얘를 또 변형 가능해보입니다?
$ AP = \begin{bmatrix} A \cdot v_1 & A \cdot v_2 \end{bmatrix} =  \begin{bmatrix} \lambda_1 \cdot v_1 & \lambda_2 \cdot v_2 \end{bmatrix} $
 
자, 여기서 아까 [단위행렬은 '모든 벡터를 자기 자신으로 보존'하는 유일한 선형변환]이라고 했습니다.
즉, 이 단위행렬에 어떤 벡터하나가 곱해졌을 때 자기 자신이 나온다는 말이죠.
그럼 이 단위행렬이 스칼라배가 되면, 당연히 어떤 벡터도 방향은 그대로이고 스칼라배가 된 벡터가 나오겠죠?
자, 근데 여기서 벡터가 쌓인 행렬이 곱해지면 어떻게 될까요?
 
가령
$ \begin{bmatrix} v_1 & v_2 \end{bmatrix} \begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix} = \begin{bmatrix} v_1 & v_2 \end{bmatrix} $
이건 자명하죠? 결국 [단위행렬은 '모든 벡터를 자기 자신으로 보존'하는 유일한 선형변환]이 맞네요
그렇다면 일정 스칼라배 한건?
$ \begin{bmatrix} v_1 & v_2 \end{bmatrix} \begin{bmatrix} 5&0 \\ 0&5 \end{bmatrix} = \begin{bmatrix} 5 \cdot v_1 & 5 \cdot v_2 \end{bmatrix} $
오, 역시 벡터의 배수배가 되는군요? 그럼 좀 더 나아가서 단위행렬이 아니라, 대각선으로 다른 값을 주면 각 벡터마다 곱해지는 배수가 달라지겠네요?
$ \begin{bmatrix} v_1 & v_2 \end{bmatrix} \begin{bmatrix} 2&0 \\ 0&5 \end{bmatrix} = \begin{bmatrix} 2 \cdot v_1 & 5 \cdot v_2 \end{bmatrix} $
오~ 그럼 다시 돌아가서
$ AP = \begin{bmatrix} \lambda_1 \cdot v_1 & \lambda_2 \cdot v_2 \end{bmatrix} $
이친구를 다시 보면...
오!
$ AP = \begin{bmatrix} v_1 & v_2 \end{bmatrix} \begin{bmatrix} \lambda_1 & 0\\ 0 & \lambda_2 \end{bmatrix} $
이렇게 변환이 되겠군요!
그리고 우리는 이 결과로부터 아주 재밌는 결과도 같이 얻었습니다! 네! 결국 대각선인 행렬을 찾아냈어요!
 
이 대각선 행렬을 D라고 해볼께요!
그럼 수식은
$ AP = A \begin{bmatrix} v_1 & v_2 \end{bmatrix} = \begin{bmatrix} A \cdot v_1 & A \cdot v_2 \end{bmatrix} =  \begin{bmatrix} \lambda_1 \cdot v_1 & \lambda_2 \cdot v_2 \end{bmatrix} = \begin{bmatrix} v_1 & v_2 \end{bmatrix} \begin{bmatrix} \lambda_1 & 0\\ 0 & \lambda_2 \end{bmatrix} = PD $
$ AP = PD $가 되겠죠!
여기서 P의 역행렬을 좌우변 모두 곱해주면!
$ A = PDP^{-1} $
와! 결국 companion matrix를 연역적 방법으로 대각행렬로 변환하는데 성공하였습니다!!!
 
그리고 이 변형에는 아주 재밌는 특성이 있는데요
$ A^2 = (PDP^{-1}) \cdot (PDP^{-1}) $이 되잖아요? 근데 $ P^{-1}P $는 상쇄되니까
$ A^2 = PDDP^{-1}  = PD^2P^{-1} $이 되면서, 결국 대각행렬만 제곱이 되는 꼴이 된답니다!
그럼 대각행렬의 거듭제곱은 뭐다? 요소의 거듭제곱으로 나타낼 수 있다!
와! 해결!
그럼 우리 companion matrix의 거듭제곱 문제가 해결되었어요!
 

2-5. 대각행렬로 다시나타내기

아까 
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = A^{n-1} \cdot \begin{bmatrix} 1\\0 \end{bmatrix} $
요렇게 깔끔하게 정리된 식을 얻었으나, 결국 companion matrix의 거듭제곱에 막혔던 것을 이번에 우리는 쉽게 파고들 수 있습니다.
$ A^{n-1} = PD^{n-1}P^{-1} $
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = PD^{n-1}P^{-1} \cdot \begin{bmatrix} 1\\0 \end{bmatrix} $
이제 진짜로 식을 풀어봅시다
 
 

3. 결론

여기서 $ P^{-1} $은
$ P^{-1} = \frac{1}{\lambda_1 - \lambda_2} \begin{bmatrix} 1&-\lambda_2 \\ -1 & \lambda_1 \end{bmatrix} $
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \overbrace{\begin{bmatrix} \lambda_1 & \lambda_2 \\ 1&1 \end{bmatrix}}^P \overbrace{\begin{bmatrix} \lambda_1^{n-1}&0\\0&\lambda_2^{n-1} \end{bmatrix}}^{D^{n-1}} \cdot \overbrace{\frac{1}{\lambda_1 - \lambda_2} \begin{bmatrix} 1&-\lambda_2 \\ -1 & \lambda_1 \end{bmatrix}}^{P^{-1}} \cdot \begin{bmatrix} 1\\0 \end{bmatrix} $
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \frac{1}{\lambda_1 - \lambda_2} \cdot \begin{bmatrix} \lambda_1 & \lambda_2 \\ 1&1 \end{bmatrix}\begin{bmatrix} \lambda_1^{n-1}&0\\0&\lambda_2^{n-1} \end{bmatrix} \begin{bmatrix} 1&-\lambda_2 \\ -1 & \lambda_1 \end{bmatrix} \cdot \begin{bmatrix} 1\\0 \end{bmatrix} $
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \frac{1}{\lambda_1 - \lambda_2} \cdot \begin{bmatrix} \lambda_1^{n}&\lambda_2^{n} \\ \lambda_1^{n-1}&\lambda_2^{n-1}\end{bmatrix} \begin{bmatrix} 1&-\lambda_2 \\ -1 & \lambda_1 \end{bmatrix} \cdot \begin{bmatrix} 1\\0 \end{bmatrix} $
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \frac{1}{\lambda_1 - \lambda_2} \cdot \begin{bmatrix} \lambda_1^{n}&\lambda_2^{n} \\ \lambda_1^{n-1}&\lambda_2^{n-1}\end{bmatrix} \begin{bmatrix} 1\\-1 \end{bmatrix} $
$ \begin{bmatrix} F_n\\F_{n-1} \end{bmatrix} = \frac{1}{\lambda_1 - \lambda_2} \cdot \begin{bmatrix} \lambda_1^{n}-\lambda_2^{n} \\ \lambda_1^{n-1}-\lambda_2^{n-1}\end{bmatrix} $
그리고 여기서 우리는 $ F_n $ 성분만 필요하므로 (개념적으로는 1번 요소만 꺼내서 쓰면 될 것이고, 수식적으로는 양변에 [1 0]을 곱해주면 될 것이다)
$ F_n = \frac{1}{\lambda_1 - \lambda_2} (\lambda_1^{n}-\lambda_2^{n}) $
여기서, $ \lambda_1 = \frac{1+\sqrt5}{2}, \; \lambda_2 = \frac{1-\sqrt5}{2} $이므로
 
$ F_n = \frac{1}{\sqrt5} \left(\left(\frac{1+\sqrt5}{2}\right)^{n}-\left(\frac{1-\sqrt5}{2}\right)^{n}\right) $
 
와! 선형대수로 피보나치 수열 풀기 성공!

선형대수[Linear Algebra]: 행렬곱셈(Matrix multiplication)의 개념 정리

1. 서론

선형대수를 하면서 사실 제일 큰게 수를 다루는 '감각'이 아닌가 싶다.

'엄밀하게 왜이래?'를 따지는 것도 중요하지만, 사실은 약간 '어~ 이게 이러니까 이렇게 되네? 오 쫌 재밌네?'하면서 받아들이고 사용하다보면 나중에 크게 이해되는 때가 오기도 한다.(그리고 그건 어떤 내부적이든 외부적이든 깨달음의 순간이 왔을 때 익숙했었어야지만이 깨달을 수 있다는 부분이기도 하다..)

그리고 선형대수는 아주 재밌게도, 직관적으로 '어 이거 되는거 아냐?'했을 때 되는 경우가 굉장히 많다. 사실 그래서 선대 수학자들이 '이게 왜 돼!?!?'하면서 연구를 더욱 더 심도있게 진행시키지 않았을까~ 하는 생각도 든다.

그래서 결론은 다른 고급(?)선형대수를 들어가기 전에, 가장 기본적인 행렬 곱셈의 개념부터 한번 정리하고 가면 좋겠다고 생각을 했다.

우리가 흔하게 아는 고등학교 때 배웠던 요소별로 채워넣는 행렬곱셈 말고도 행렬을 가로로(열로) 세로로(행으로) 찢어서 계산도 가능하다는 아주 재밌는 사실이 있기 때문이다.

2. 행렬의 곱셈방식은 몇가지?

그렇다면 행렬의 곱셈방식은 몇가지나 있을까?

물론 '방식'이 여러가지 인거지, '답'은 하나다.

결론부터 말하자면 곱셈방식은 사실 네가지다.

행렬을 행과 열로 찢어서 조합할 수 있다고 하면, 꽤나 많은 경우의 수가 나오겠지만

행렬곱셈을 수행하면 그 대원칙인 $ \sum row * column $가 수행되고, 따라서 (n x m) * (m x k) = (n x k)의 행렬이 나온다는 것만 알고 있으면 경우의 수는 사실 아래의 네가지로 귀결된다.

행(row) * 열(column), 행렬(matrix) * 열(column), 행(row) * 행렬(matrix), 열(column) * 행(row)

두 행렬을 모두 행과 열로 찢어서 곱해 볼 수 있는 두가지 방식이 있을 것이고

또 다른 하나는 한 행렬 전체를 다른 행렬을 찢어서 곱해볼 수 있을 것이다.

그렇다면 남은 건 하나. '진짜 되는가?'이다.

사실 '개념'적으로 저렇게 나눠 놓은거지, 사실 실제 계산을 하면 결국 $ \sum row * column $이 수행되기때문에 결과는 항상 모두 같을 수 밖에 없다. 다만 저런 개념을 알고 있으면 행렬 곱셈을 조작할 때 좀더 자유롭게 조작이 가능해진다는 장점?

3. 간단한 행렬로 진짜 되는지 보기

$ A = \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix} $

$ B = \begin{bmatrix} 1&2\\ 1&3 \end{bmatrix} $

두 행렬을 가지고 $ A * B = C $를 해 볼 예정입니다.

3-1. row * column

가장 기본적인 행렬 곱셈 방식이죠.

$ C = \begin{bmatrix} a_{11}*b_{11}+a_{12}*b_{21}&a_{11}*b_{12}+a_{12}*b_{22}\\ a_{21}*b_{11}+a_{22}*b_{21}&a_{21}*b_{12}+a_{22}*b_{22} \end{bmatrix} $

$ \quad \, = \begin{bmatrix} 1*1+2*1&1*2+2*3\\ 3*1+4*1&3*2+4*3 \end{bmatrix} $

$ \quad \, = \begin{bmatrix} 3&8\\ 7&18 \end{bmatrix} $

3-2. matrix * column

여기서부터 재밌어집니다. matrix*column은 결과를 column으로 내보내고, 그렇기 때문에 결과에서 column으로 stack됩니다.

$ C = \begin{bmatrix} A*\begin{bmatrix} 1\\1 \end{bmatrix} & A*\begin{bmatrix} 2\\3 \end{bmatrix} \end{bmatrix} $

$ \quad \, = \begin{bmatrix} \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}*\begin{bmatrix} 1\\1 \end{bmatrix} & \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}*\begin{bmatrix} 2\\3 \end{bmatrix} \end{bmatrix} $

$ \quad \, = \begin{bmatrix} 3&8\\ 7&18 \end{bmatrix} $

3-3. row * matrix

row * matrix는 결과를 row로 내보내고, 결과적으로 row로 stack됩니다.

$ C = \begin{bmatrix} \begin{bmatrix} 1&2 \end{bmatrix}*B \\ \begin{bmatrix} 3&4 \end{bmatrix}*B \end{bmatrix} $

$ \quad \, = \begin{bmatrix} \begin{bmatrix} 1&2 \end{bmatrix} * \begin{bmatrix} 1&2\\ 1&3 \end{bmatrix} \\ \begin{bmatrix} 3&4 \end{bmatrix} * \begin{bmatrix} 1&2\\ 1&3 \end{bmatrix} \end{bmatrix} $

$ \quad \, = \begin{bmatrix} 3&8\\ 7&18 \end{bmatrix} $

3-4. column * row

두 행렬을 일반적인 행렬 곱셈 방식인 row*column이 아닌 반대로 column*row로 찢어서 계산합니다.

위의 행렬을 기준으로 보면 column*row로 계산하게되면 (2, 1) x (1, 2)가 되므로 (2, 2)의 확장이 일어나는 것과 마찬가지 결과가 생깁니다.

찢어서 계산했을 때 matrix가 2x2로 확장되므로, 결과값을 더해줍니다.

$ C = \begin{bmatrix} 1\\3 \end{bmatrix}*\begin{bmatrix} 1&2 \end{bmatrix} + \begin{bmatrix} 2\\4 \end{bmatrix}*\begin{bmatrix} 1&3 \end{bmatrix} $

$ \quad \, = \begin{bmatrix} 1&2\\3&6 \end{bmatrix} + \begin{bmatrix} 2&6\\4&12 \end{bmatrix} $

$ \quad \, = \begin{bmatrix} 3&8\\ 7&18 \end{bmatrix} $

4. 결론

이것으로 결국 어떤 방식으로 곱하든 결과는 같다는 걸 알았습니다.

반대로, 결과가 같다면 여러 방법으로 행렬의 곱셈을 조작해 볼 수 있습니다.

사이클로이드의 면적구하기(면적분)

사이클로이드(Cycloid) 시리즈 목차

• 사이클로이드(Cycloid)의 길이 구하기 (선적분)
• 사이클로이드의 면적 구하기 (면적분)
• 사이클로이드(Cycloid)의 부피 구하기 (회전체적분, 부피적분)
• 사이클로이드(Cycloid) 회전체의 표면적(겉넓이) 구하기 (회전체적분, 겉넓이적분)

말머리-

사이클로이드를 아주 뽕을 뽑아 먹어보자구요!

1탄 사이클로이드 선적분

에 이어 2탄 사이클로이드의 면적을 구해봅시다.

수식세우기-

직사각형의 면적은 어떻게 구하죠? 그렇죠 가로 곱하기 세로입니다.

곡선의 면적은요? 애매하죠?

여기서 정말 미세하게 나눠서 직사각형의 면적을 구한다음에 다 합치면? 곡선의 아래 면적이 되겠죠?

자, 가봅시다



각 위치에서 높이는 고정인데, 그 밑변만 아주아주 작게 잘라서 직사각형 구하고 다 합치면 되겠죠? 식으로 써 봅시다



직사각형 구하고

$ y dx $



다 합칩니다

$ \int y dx $



이렇게 쓸 수 있겠네요?



1탄에서 사이클로이드 매개변수로 어떻게 표현한다고 했죠?



$ x = r(t-sin t) $
$ y = r(1-cos t) $



저번처럼 미분하면~



$ dx = r(1-cos t) dt $

$ dy = rsin t dt $



그대로 대입해서 매개변수로 나타내 봅시다.



$ \int_{0}^{2\pi} y * dx $

$ \int_{0}^{2\pi} r(1-cos t) * r(1-cos t) dt $
$ r^2 \int_{0}^{2\pi} (1-cos t)^2 dt $

$ r^2 \int_{0}^{2\pi} (1-2cos t+cos^2 t) dt $
$ r^2 \int_{0}^{2\pi} (1-2cos t+\frac{cos 2t+1}{2}) dt $
$ r^2 \int_{0}^{2\pi} (\frac{3}{2}-2cos t+\frac{cos 2t}{2}) dt $

$ r^2 \frac{3}{2}t]_{0}^{2\pi} \because cos\ t, cos\ 2t $함수는 0에서 $ 2\pi $까지 적분하면 $ \pm 0 $

$ 3 \pi r^2 $

결론-

즉, 사이클로이드의 넓이는 원 넓이의 세배!

직선 두개로 뢸로 삼각형(Reuleaux triangle) 4등분 하기[그러나 이제 적분이 없는]

[나야 기하학]

말머리-

어제 뢸로 삼각형을 해체했다는 기쁨도 잠시... 어제 포스팅 쓰면서 적분 변환하느라 아주 길고 긴 latex을 작성했던 것이 떠올랐다.

근데 적분 말고, 전에 원을 나눌때도 기하학으로 하면 더 편했던 것 처럼 기하학으로는 안될까..?

싶었는데... 고민해보니 되긴하네!? 해서 시작한 포스팅이네요

하다보니 항이 많고, 원 변수를 모두 포함해서 계산하자면 아주 복잡해지는데 이를 적당히 간단한 변수로 치환치환 해가며 정리하면 금새 수식이 정리되는게, 정말 복잡한 적분 없이 바로 결과식에 도달하는게 재미지네요!

수식세우기-

1] 도형 나누기

이전 포스팅인 >>적분으로 뢸로삼각형 4등분하기<<를 기본으로 보시면 좋습니다.

기본 뼈대는 같습니다. 뢸로삼각형 넓이의 $ \frac{1}{4} $을 구하는 거지요.

그러나 기하학을 곁들여서 생각해보면 이번에는 뢸로삼각형을 아래와 같이 나눠볼 수 있을 것 같네요!

예 색칠을 좀 해봤습니다!

저 자주색 영역이(빗금까지 포함해서) 부채꼴입니다. 뢸로 삼각형의 정의가 한 꼭지점을 원점으로하여 다른 두 꼭지점을 연결하는 원의 일부분을 그리는 것이었으니 당연히 한 꼭지점을 원점으로하는 자주색 영역은 부채꼴이 됩니다.

다만 여기서는 임의의 각 $ \theta $만큼의 부채꼴인거죠.

자 그러면 이제 뢸로삼각형의 영역의 $ \frac{1}{4} $의 넓이를 저 도형들로 살펴보죠!

먼저 자주색 부채꼴 넓이에서 빨간색 삼각형 넓이를 빼고 파란색 삼각형 넓이를 더하고 주황색 활꼴의 절반 넓이를 더하면 뢸로 삼각형의 1/4이 되겠네요!

똑같이 뢸로삼각형의 내부 정삼각형의 밑변을 y=0에 두고, 그 높이를 a라고 칭하겠습니다.

그리고 a높이에서 x위치는 이전 포스팅과 동일하게 원의 방정식으로 놓겠습니다.

그러면,

$ 자주-빨강+파랑+주황 = \frac{1}{4} 뢸로삼각형 전체 넓이 $

으로 볼 수 있고, 이거를 좀 더 있어보이게 표현해보면 아래와 같습니다.

$ A_{Sector}-A_{SectorTriangle}+A_{UpperTriangle}+\frac{1}{2}A_{Segment} = \frac{1}{4}A_{ReuleauxTriangle} $

자, 이제 각각의 넓이를 구하러 출동해보시죠

2] 각각의 넓이 구하기

차례대로 하나씩 넓이를 구해보죠

일단 자주색 부채꼴입니다.

임의의 각 $ \theta $로 계산하면 부채꼴의 넓이는

$ A_{Sector} = \frac{1}{2}d^2\theta $

이렇게 되겠죠?

다음은 빨간 삼각형입니다.

삼각형의 넓이는 밑변*높이*절반 입니다. 여기서 밑변은 폭의 절반이지만, 높이는 일반각 $ \theta $로 정의되기때문에 밑변에 $ tan\theta $를 곱한 것으로 알 수 있죠. 따라서

$ A_{SectorTriangle} = \frac{1}{2}*\frac{1}{2}d*\frac{1}{2}dtan\theta $

이 됩니다.

파란 삼각형을 보죠

빨간 삼각형과 비슷하게 밑변*높이*절반을 가져가려하나, 밑변에 해당하는 길이가 변수 a에 의해서 계속 변화합니다. 따라서 밑변은 변수 a에 의해 길이가 결정되는데, 이 법칙을 나타낸게 원의 방정식을 정리한 함수죠. 자세한 내용은 이전 포스팅에 있으니 여기서는 빠르게 수식을 세워보도록 하겠습니다.

그리고 이 파란 삼각형에서도 높이는 밑변에 tan값을 곱한 값이 되는데, 여기서 일반각은 평행한 두 직선 사이 엇각의 관계가 되므로(정확히는 내엇각(alternate interior angle)) 똑같이 $ \theta $가 됩니다.

수식으로 세워보면

$ A_{UpperTriangle} = \frac{1}{2}*(\sqrt{d^2-a^2}-\frac{d}{2})*(\sqrt{d^2-a^2}-\frac{d}{2})tan\theta $

이 됩니다.

대망의 활꼴의 절반인 주황색이 나왔습니다. 

전체 활꼴의 넓이는 아래와 같고

$ A_{Segment} = \frac{1}{2}d^2\frac{\pi}{3}-\frac{\sqrt{3}}{4}d^2 $

이것의 절반이 주황색의 넓이죠?

전체 수식에서 나중에 1/2을 해줄테니 수식은 여기까지 세우는 걸로 하죠

마지막 뢸로 삼각형의 넓이 입니다.

$ A_{ReuleauxTriangle} = \frac{3}{2}d^2\frac{\pi}{3}-\frac{\sqrt{3}}{2}d^2 $

부채꼴넓이*3-정삼각형넓이*2 해주면 나옵니다.

이제 각각의 넓이를 다 구했으니 다 합칠까요?

아뇨... 각각만 봐도 너무 복잡한데 지금 다 합쳐버리면 길이가 너무 길어져요...

그러니 동일하게 각각 다 수식을 정리해서 마지막에 합쳐보죠!

3] 수식 정리하기

$ \frac{a}{d} = s $ 로 놓겠습니다. 그럼 $ a = ds $도 성립하겠죠?

그리고 sin함수의 정의는 임의의 각 $ \theta $에 대해 그 직각삼각형의 $ \frac{높이}{빗변} $로 정의됩니다. 따라서
$ sin\theta = \frac{a}{d} $ 가 되겠네요. 그리고 $ \frac{a}{d} = s $니까, 삼단논법으로 $ sin\theta = s $입니다.

sin을 정의했으니 다른 삼각함수들도 정의해보죠. 삼각함수들은 하나가 정해지면 다른것들로도 다 변환이 된답니다.
$ cos\theta = \sqrt{1-sin^2\theta} = \sqrt{1-s^2} $
$ tan\theta = \frac{sin\theta}{cos\theta} = \frac{s}{\sqrt{1-s^2}} $

자, 이제 간단하게 할 준비는 다 끝났습니다. 수식정리하러가죠

부채꼴은 다음과 같이 정리될겁니다. $ sin\theta=s $면 $ \theta=arcsin\ s $겠죠?

$ A_{Sector} = \frac{1}{2}d^2\theta $
$ A_{Sector} = \frac{1}{2}d^2arcsin\ s $

빨간삼각형은

$ A_{SectorTriangle} = \frac{1}{2}*\frac{1}{2}d*\frac{1}{2}dtan\theta $
$ A_{SectorTriangle} = \frac{d^2s}{8\sqrt{1-s^2}} $

파란삼각형은

$ A_{UpperTriangle} = \frac{1}{2}*(\sqrt{d^2-a^2}-\frac{d}{2})*(\sqrt{d^2-a^2}-\frac{d}{2})tan\theta $
$ A_{UpperTriangle} = \frac{d^2}{2}(\sqrt{1-s^2}-\frac{1}{2})^2\frac{s}{\sqrt{1-s^2}} $

요렇게 정리가 되겠네요!

활꼴과 뢸로 삼각형도 각각 절반, 사등분 해준 결과를 먼저 써서 정리하죠

$ \frac{1}{2}A_{Segment} = \frac{d^2}{4}(\frac{\pi}{3}-\frac{\sqrt{3}}{2}) $
$ \frac{1}{4}A_{ReuleauxTriangle} = \frac{d^2}{8}(\pi-\sqrt{3}) $

이 두개는 상수항이므로 먼저 계산을 통해 정리해보도록 하겠습니다.

$ A_{Sector}-A_{SectorTriangle}+A_{UpperTriangle}+\frac{1}{2}A_{Segment} = \frac{1}{4}A_{ReuleauxTriangle} $

이게 전체식이구요, 상수항을 이항해서

$ A_{Sector}-A_{SectorTriangle}+A_{UpperTriangle} = \frac{1}{4}A_{ReuleauxTriangle}-\frac{1}{2}A_{Segment} $

요렇게 놓은뒤에 위에서 정리한 식을 넣고 다시 정리하면

$ A_{Sector}-A_{SectorTriangle}+A_{UpperTriangle} = \frac{d^2\pi}{24} $

요렇게 상수항이 깔끔해집니다.

이제 나머지 식들을 대입해보죠

$ \frac{1}{2}d^2arcsin\ s-\frac{d^2s}{8\sqrt{1-s^2}}+\frac{d^2}{2}(\sqrt{1-s^2}-\frac{1}{2})^2\frac{s}{\sqrt{1-s^2}} = \frac{d^2\pi}{24} $

길어졌죠? 일단 공통되는 변수를 양변 나눠줘서 일단 최대한 간단하게 해봅시다.

$ \frac{d^2}{2} $로 양변 나누면(=$ \frac{2}{d^2} $로 양변 곱하면)

$ arcsin\ s-\frac{s}{4\sqrt{1-s^2}}+(\sqrt{1-s^2}-\frac{1}{2})^2\frac{s}{\sqrt{1-s^2}} = \frac{\pi}{12} $

훨씬 간단해졌죠?

그래도 루트가 있으니까 뭔가 보기 불편합니다. 더 줄여보죠. $ u = \sqrt{1-s^2} $ 이렇게 루트를 치환해보겠습니다.

$ arcsin\ s-\frac{s}{4u}+(u-\frac{1}{2})^2\frac{s}{u} = \frac{\pi}{12} $

보기 훨씬 편하죠?

이제 세번째 항의 제곱을 풀어봅시다. 아주 수식이 간단하니 그 옆에 있는 곱셈으로 연결된 부분까지 같이 곱해주죠. 이렇게 간단하게 놓은 상황에서 풀면 간단하지만, 처음부터 풀어버리려면 아주 복잡했겠죠?

$ arcsin\ s-\frac{s}{4u}+(su-s+\frac{s}{4u}) = \frac{\pi}{12} $

보면 $ \frac{s}{4u} $가 덧셈 뺄셈으로 있네요? 소거해주면

$ arcsin\ s+su-s = \frac{\pi}{12} $

와우 엄청 간단한 식이 나왔네요

이제 줄이고 줄인 식이니까, 다시 치환한 변수들을 원래 변수들로 돌려주죠.

일단 u를 다시 s로,

$ arcsin\ s+s\sqrt{1-s^2}-s = \frac{\pi}{12} $

그리고 s를 다시 a와 d로 바꿔줍니다.

$ arcsin \frac{a}{d}+\frac{a}{d}\sqrt{1-\left(\frac{a}{d}\right)^2}-\frac{a}{d} = \frac{\pi}{12} $

그러면!!

바로 적분으로 풀었던 식과 완전 동일한 식이 짜잔 하고 나타난답니다.

결론-

조금 번거롭지만 복잡한 적분 없이도 풀 수 있었던 것이었습니다!