무한서고

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

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

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

0. 서론

자 오늘은 대망의 마지막시간!

사이클로이드의 선 길이, 넓이, 회전체 부피까지 알아봤으면 그다음은 무엇? 바로바로 표면적이다~

그럼 바로 알아보도록하죠~

1. 어떻게 구할건데?

표면적은 원기둥의 옆 넓이에서 힌트를 얻어보면 되는데, 원기둥의 옆 넓이는 원기둥의 원주길이($ 2 \pi r $)에다가 높이를 곱한 것이잖아요?

그러면 이걸 그래프로 가져와보면~

저번에 구하면서 생각해 봤듯이 이 회전체는 아주 얇은 원판으로 이루어져 있을테니 이 원판의 옆넓이를 구해보면 되겠슴다.

원판의 옆 넓이는 위에서 봤듯이 원주길이에 높이를 곱한것인데, 적분을 하려면 여기서 일반적인 높이 대신 미소높이(아주아주 작은 높이)를 곱해주면 되겠죠?

자 회전체에서 원판의 반지름은 바로 $ y $죠, 그리고 높이는? 전에 선 길이를 적분할때처럼 아주 미소한 변화량만큼의 곡선길이 일겁니다.($ \sqrt{dx^2 + dy^2} $)

그리고 이거를 매개변수 $ t $에 대해서 0부터 $ 2 \pi $까지 싹 모으면 짜잔, 옆넓이 즉 표면적이 나오겠군요!

2. 구해보자

즉, $ r = y, \ y = r(1 - \cos t), \ dh = \sqrt{dx^2 + dy^2}  $ 여기서 dh는 미소 높이를 의미합니다.

식으로 써보면

$ S = \int_0^{2\pi} 2\pi y \ dh $

$ S = 2 \pi \int_0^{2 \pi} y * \sqrt{(\frac{dx}{dt})^2 + (\frac{dy}{dt})^2} \ dt $

$ S = 2 \pi r \int_0^{2 \pi} (1 - \cos t) * \sqrt{(\frac{dx}{dt})^2 + (\frac{dy}{dt})^2} dt $

이렇게 매개변수 식이 최종적으로 정리가 되겠습니다.

여기서, $ \frac{dx}{dt}=r(1 - \cos t,) \ \frac{dy}{dt} = r\sin t $ 니까

$ S = 2 \pi r \int_0^{2 \pi} (1 - \cos t) * r\sqrt{(1 - \cos t)^2 + (\sin t)^2} dt $

$ S = 2 \pi r^2 \int_0^{2 \pi} (1 - \cos t) * \sqrt{(1 - \cos t)^2 + (\sin t)^2} dt $

$ (1 - \cos t)^2 $ 풀어주고,

$ S = 2 \pi r^2 \int_0^{2 \pi} (1 - \cos t) * \sqrt{1 - 2\cos t + (\cos t)^2 + (\sin t)^2} dt $

$ (\cos t)^2 + (\sin t)^2 = 1 $이니까

$ S = 2 \pi r^2 \int_0^{2 \pi} (1 - \cos t) * \sqrt{1 - 2\cos t + 1} dt $

$ S = 2 \pi r^2 \int_0^{2 \pi} (1 - \cos t) * \sqrt{2 - 2\cos t} dt $

$ S = 2 \pi r^2 \int_0^{2 \pi} (1 - \cos t) * \sqrt{2(1 - \cos t)} dt $

$ S = 2 \pi r^2 \int_0^{2 \pi} (1 - \cos t) * \sqrt{2(2\sin^2 \frac{t}{2})} dt \quad \leftarrow \cos (\frac{t}{2}+\frac{t}{2}) = \cos^2 \frac{t}{2} + \sin^2 \frac{t}{2} = 1 - 2\sin^2 \frac{t}{2} = 2\cos^2 \frac{t}{2} -1 $

$ S = 4 \pi r^2 \int_0^{2 \pi} (1 - \cos t) * \sqrt{\sin^2 \frac{t}{2}} dt $

원래 $ \sqrt{A^2} = |A| $지만, 적분 구간 $ t \in [0, 2\pi] $에서 $ \frac{t}{2} $의 범위는 $ [0, \pi] $가 되고, 이 범위에서 $ \sin \frac{t}{2} \ge 0$ 이므로 절댓값 없이 정리가 가능합니다.

$ S = 4 \pi r^2 \int_0^{2 \pi} (1 - \cos t) * \sin \frac{t}{2} dt $

아까와 마찬가지로 $ \cos t = 1 - 2\sin^2 \frac{t}{2} $로 바꿔주면,

$ S = 4 \pi r^2 \int_0^{2 \pi} 2 \sin^2 \frac{t}{2} * \sin \frac{t}{2} dt $

$ S = 8 \pi r^2 \int_0^{2 \pi} \sin^2 \frac{t}{2} * \sin \frac{t}{2} dt $

$ S = 8 \pi r^2 \int_0^{2 \pi} \sin^3 \frac{t}{2} dt $

이렇게 간단하게 정리가 됩니다.

그런데, 저번에도 말씀드렸다시피 삼각함수의 세제곱은 바로 적분으로 풀 수가 없으니 찢어줍시다.

$ S = 8 \pi r^2 \int_0^{2 \pi} \sin^2 \frac{t}{2} * \sin \frac{t}{2} dt $

삼각함수 항등식에서 $ (\cos t)^2 + (\sin t)^2 = 1 $이니까 $ (\cos \frac{t}{2})^2 + (\sin \frac{t}{2})^2 = 1 $이겠죠?

$ S = 8 \pi r^2 \int_0^{2 \pi} (1 - \cos^2 \frac{t}{2}) * \sin \frac{t}{2} dt \quad \leftarrow \cos \frac{t}{2} = u, -\frac{1}{2} \sin \frac{t}{2} dt = du \Leftrightarrow \sin \frac{t}{2} dt = -2du $

그리고나서 치환해줍니다.

$ S = 8 \pi r^2 \int (1 - u^2) * (-2) du $

이제 엄청 쉽게 풀릴 일만 남은 것 같죠?

아, 저번처럼 치환했다가 다시 돌아올거라 아래끝 위끝은 치환값으로 계산 안합니다.

치환 하고 적분한 다음 다시 원래대로 안돌리고 그 상태에서 값을 구하기위해 하는게 사실상 아래끝 위끝 값을 치환값으로 바꿔주는건데, 저희는 그냥 적분 후 다시 삼각함수로 돌리겠습니다.(즉, 아래끝 위끝 치환값은 계산 안하고 진행)

$ S = -16 \pi r^2 \int (1 - u^2) du $

$ S = -16 \pi r^2 (\int 1 du - \int u^2 du) $

$ S = -16 \pi r^2 (u - \frac{1}{3}u^3) $

$ S = -16 \pi r^2 (\cos \frac{t}{2}]_0^{2 \pi} - \frac{1}{3}(\cos \frac{t}{2})^3]_0^{2 \pi}) \quad \leftarrow \cos \frac{t}{2} = u $

보시다시피, 치환값을 다시 원래대로 돌립니다. 적분구간은 그대로겠죠?

$ S = -16 \pi r^2 ((-1 - 1) - \frac{1}{3}(-1 - 1)) $

$ S = -16 \pi r^2 (-2 + \frac{2}{3}) $

$ S = -16 \pi r^2 (-\frac{6}{3} + \frac{2}{3}) $

$ S = -16 \pi r^2 * -\frac{4}{3} $

$ S = \frac{64}{3} \pi r^2 $

3. 결론

따라서, 사이클로이드의 회전체의 표면적(겉넓이)는 $ \frac{64}{3} \pi r^2 $ 이라는 것이 밝혀졌습니다!

사이클로이드(Cycloid)의 부피 구하기(회전체적분, 부피적분)

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

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

0. 서론

우리는 앞서 사이클로이드의 호의 길이(사이클로이드(Cycloid)의 길이 구하기(선적분))와 면적(사이클로이드의 면적구하기(면적분))을 구해보았습니다.

이번엔 세번째 시간으로 사이클로이드의 부피에 대해서 알아봅시다!

1. 부피?

사이클로이드는 2차원 평면에 있는데 왠 부피?라고 하신다면, 적분에는 항상 따라붙는 세가지가 선적분! 면적분! 회천체적분! 입니다.

즉, 2차원 평면에 있는 '면'을 x축 주위로 회전시키면 3차원 입체가 만들어지고, 그 부피를 적분으로 구할 수 있는거죠!

그리고 지금 우리는 이 사이클로이드를 x축을 기준으로 한바퀴 돌려서 소위 '럭비공'과 같은 모양으로 만들 예정입니다.

요렇게 생긴 곡선을

x축 기준으로 요렇게 회전시키는거죠.

대략 3D로 보면 이런 느낌이겠죠?

2. 회전체의 부피 공식 설정

자, 일단 '회전'하면 그 단면은 항상 '원'이 되겠죠?

그럼 적분의 모토와도 같이, 면을 쫘좌좌좍 모아가면 부피가 되겠네요!(뭐, 엄밀히는 면*미소높이 하여 아주 작은 원통들을 모아가는 거겠지만요..)

일단 원의 넓이는 $ \pi r^2 $으로 정의됩니다. 여기서 $ r $은 반지름이죠.

우리는 현재, x축을 기준으로 한바퀴 돌려서 만들었으니, 반지름은 바로 이 곡선의 높이가 될 겁니다.

이전 포스팅에서 확인하실 수 있듯이 현재 이 곡선의 높이 y는 $ y = r(1-\cos t)$ 이렇게 정의 되어 있으므로,

회전체의 단면의 원의 넓이는 $ \pi r^2 = \pi (r(1-\cos t))^2$이 되겠네요.

그리고 여기서 아주 작은 미소부피(dV)를 구하기위해 원 넓이에다가 아주 미소한 높이를 곱해줘야 하겠습니다.

현재 회전체의 부피를 x축을 따라가며 구하고 있으므로 이 원통(원기둥)의 높이는 바로 $ dx $가 되겠네요.

즉, $ dV = \pi (r(1-\cos t))^2 dx $ 되겠습니다.

그리고 이 미소부피들을 싹 다 적분하면, 회전체의 부피가 나오겠죠?

즉, $ \int dV = \int \pi (r(1-\cos t))^2 dx $입니다.

그러나 여기서 본식은 매개변수 표현인데 바로 $ dx $를 써서 계산이 불가능 하기때문에, 과거 포스팅에서 정리했던 내용들을 다시 상기해보면, $ dx = r(1-\cos t)dt $입니다.

적분을 위한 준비는 끝났습니다. 다시한번 정리해보죠.

적분의 아래끝은 0 위끝은 $ 2 \pi $, $ y = r(1-\cos t)$, $ dx = r(1-\cos t)dt $

이제 이걸 이용해서 수식으로 정리해주면,

$ V = \int_0^{2 \pi} dV = \pi \int_0^{2 \pi} (r(1-\cos t))^2 r(1-\cos t) dt $

이렇게 정리가 되겠습니다.

수식은 다 세워졌네요. 이제 정리하며 풀기만하면 끝입니다.

3. 적분 계산

$ \pi \int_0^{2 \pi} (r(1-\cos t))^2 r(1-\cos t) dt $

이 수식을 다시 깔끔하게 정리하면

$ \pi r^3 \int_0^{2 \pi} (1-\cos t)^3 dt $

요렇게 세제곱 형식으로 묶을 수 있을겁니다.

그리고 세제곱을 다시 풀어주면

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

이렇게 풀 수 있고,

삼각항수 항등식에서 $ \cos^2 t = \frac{1 + \cos 2t}{2} $ 이므로

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

$ \pi r^3 \int_0^{2 \pi} (\frac{5}{2}-3\cos t+\frac{3}{2}\cos 2t-\cos^3 t) dt $

이렇게 정리가 되겠군요.

이제 적분은 선형결합에 대해 분배될 수 있으므로,

$ \pi r^3 \left( \int_0^{2 \pi} \frac{5}{2} \ dt-3\int_0^{2 \pi} \cos t \ dt+\frac{3}{2}\int_0^{2 \pi}\cos 2t \ dt-\int_0^{2 \pi} \cos^3 t \ dt \right) $

여기서, $ \cos^3 t $는 직접적으로 적분할 수가 없으니, 찢어줍시다.

$ \pi r^3 \left( \frac{5}{2} \int_0^{2 \pi} dt-3\int_0^{2 \pi} \cos t \ dt+\frac{3}{2}\int_0^{2 \pi}\cos 2t \ dt-\int_0^{2 \pi} \cos^2 t \cdot \cos t \ dt \right) $

이러면 약간의 빛이 보입니다. 삼각항수 항등식 $ \cos^2 t + \sin^2 t = 1 \Leftrightarrow \cos^2 t = 1-\sin^2 t $을 쓰면

$ \pi r^3 \left( \frac{5}{2} \int_0^{2 \pi} dt-3\int_0^{2 \pi} \cos t \ dt+\frac{3}{2}\int_0^{2 \pi}\cos 2t \ dt-\int_0^{2 \pi} (1-\sin^2 t) \cdot \cos t \ dt \right) $

그리고 $ \sin t $를 $ u $로 치환하면, 사실 치환한 아래끝 위끝이 모두 값이 0이 되면서 적분결과가 0이 되어버리지만 조금 더 수학적 재미를 위해 끝을 임의로 놓고 계산진행해보겠습니다.(구조를 보기 위해 양 끝에 임의기호 @, * 사용)

$ \pi r^3 \left( \frac{5}{2} \int_0^{2 \pi} dt-3\int_0^{2 \pi} \cos t \ dt+\frac{3}{2}\int_0^{2 \pi}\cos 2t \ dt-\int_{@}^{*} (1-u^2) du \right) \leftarrow u = \sin t,\ du = \cos t dt $

$ \pi r^3 \left( \frac{5}{2} \int_0^{2 \pi} dt-3\int_0^{2 \pi} \cos t \ dt+\frac{3}{2}\int_0^{2 \pi}\cos 2t \ dt-(\int_{@}^{*} du - \int_{@}^{*} u^2 du) \right) $

$ \pi r^3 \left( \frac{5}{2} \int_0^{2 \pi} dt-3\int_0^{2 \pi} \cos t \ dt+\frac{3}{2}\int_0^{2 \pi}\cos 2t \ dt-(u\vert_{@}^{*} - \frac{1}{3} u^3\vert_{@}^{*}) \right) $

$ \pi r^3 \left( \frac{5}{2} \int_0^{2 \pi} dt-3\int_0^{2 \pi} \cos t \ dt+\frac{3}{2}\int_0^{2 \pi}\cos 2t \ dt- \left( \sin t \vert_0^{2\pi} - \frac{1}{3} \sin^3 t \vert_0^{2\pi} \right) \right) \leftarrow u = \sin t $ (+치환에서 다시 돌아왔으니 적분구간 다시 전과 같은 구간으로 살려주기)

여기서 바로 $ \sin t $에 값 대입하면 0 나오지만, 그냥 수식 그대로 끌고가 볼께요. 이제 다 적분해줍니다.

$ \pi r^3 \left( \frac{5}{2} t \vert_0^{2 \pi} -3 \sin t \vert_0^{2 \pi}+\frac{3}{4}\sin 2t\vert_0^{2 \pi} \ dt- \sin t \vert_0^{2\pi} + \frac{1}{3} \sin^3 t \vert_0^{2\pi} \right) $

적분 풀면

$ \pi r^3 \left( \frac{5}{2} \cdot 2\pi-0+0-0+0 \right) $

즉, 살아 남은 항은 첫번째 항 뿐이므로

$ 5 \pi^2 r^3 $

이 됩니다.

사실 모든게 0으로 정리되는 걸 보여드리고 싶어 이렇게 진행했는데, 사실... 0에서 $ 2\pi $까지 $ \cos $함수의 홀수승 적분은 전부 0이라서

$ \pi r^3 \left( \int_0^{2 \pi} \frac{5}{2} \ dt-3\int_0^{2 \pi} \cos t \ dt+\frac{3}{2}\int_0^{2 \pi}\cos 2t \ dt-\int_0^{2 \pi} \cos^3 t \ dt \right) $

이렇게 정리된 순간 $ \cos $적분은 전부 사라지니 사실상 이 단계에서 계산이 끝난거나 다름없긴 합니다...

4. 결론

사이클로이드 회전체의 부피 $ V $ 는 $ 5 \pi^2 r^3 $입니다.

연산의 정의부터 군, 환, 체까지 – 닫힘성에서 시작하는 대수 구조의 세계

0. 들어가며

우리는 고등학교 수학 시간에 처음으로 연산이라는 개념을 접합니다.

특히 "자연수끼리 더하면 자연수다" 또는 "자연수끼리 나누면 자연수가 아니다"라는 식으로 연산에서 '닫혀 있다', '열려 있다'는 개념을 처음 접했던 기억이 있을 것입니다.(고등학교 수학시간에 너무 뜬금없이 나왔던 그거 말입니다..)

이렇게 연산의 성질을 분석하는 과정은 고등학교, 대학교를 지나면서 더 정교해지고 추상화됩니다.

결국 하나의 연산 혹은 여러 연산이 어떤 성질을 만족하는지를 기준으로, 군(group), 환(ring), 체(field) 같은 수학적 구조로 발전하게 됩니다.

1. 연산이란?

연산(operation)이란, 어떤 집합에 정의된 규칙으로서, 집합의 원소들을 입력받아 결과를 내는 함수입니다.

• 단항 연산: 원소 1개 → 예: 음수, 제곱근
• 이항 연산: 원소 2개 → 예: 덧셈, 곱셈

가장 흔한 이항 연산의 예는 다음과 같습니다:

• 정수의 덧셈: ∀a,b∈ℤ, a + b ∈ ℤ → 닫혀 있음 (여기서 ∀는 '모든' 이라는 뜻이고, ∈는 속한다는 뜻입니다)
• 자연수의 뺄셈: 3 - 5 = -2 ∉ ℕ → 닫혀 있지 않음

2. 연산의 성질

이항 연산에 대해 주요하게 다루는 성질은 다음과 같습니다:

• 닫힘성: 결과가 다시 같은 집합에 속함
• 결합법칙: (a * b) * c = a * (b * c)
• 항등원: a * e = a = e * a
• 역원: a * a⁻¹ = e
• 교환법칙: a * b = b * a

3. 주요 대수적 구조 비교표

※ 참고: 모든 곱셈 결과가 0이 되는 '제로환(zero ring)'이라는 극단적인 구조도 있으나, 보통은 정역이나 체와 같은 구조에 포함되지 않으므로 이 글에서는 생략합니다.

4. 예시로 보는 구조들

• ℕ (자연수): 덧셈에 대해 닫혀 있음 → 반군
• ℤ (정수): 덧셈에 대해 아벨군, 곱셈은 결합법칙만 → 환
• ℚ (유리수): 덧셈과 곱셈 모두 아벨군 (0 제외) → 체
• n × n 정방행렬: 덧셈에 대해 아벨군, 곱셈에 대해 모노이드 → 환(종합적으로)

5. 마무리

하나의 연산으로부터 시작해 여러 가지 성질을 차례로 추가하면, 대수학의 주요한 구조들이 자연스럽게 나타납니다.

마그마 → 반군 → 모노이드 → 군 → 아벨군 → 환 → 정역 → 체 순으로 점점 더 많은 조건이 요구됩니다.

이러한 분류는 단순히 집합과 연산의 조합이 아니라, 구조 전체가 어떤 논리적 규칙을 따르는지를 보여주는 강력한 언어입니다.

우리가 흔히 다루는 숫자나 행렬도 사실 이 구조의 일부이며, 연산의 정의와 성질을 이해함으로써 훨씬 깊이 있는 수학 공부가 가능해집니다.

6. 참고 수식

• 연산의 닫힘성: ∀a, b ∈ S, a * b ∈ S  
• 결합법칙: (a * b) * c = a * (b * c)  
• 항등원: ∃e ∈ S, ∀a ∈ S, e * a = a * e = a  (∃표시는 ~가 존재할때 라는 뜻입니다)
• 역원: ∀a ∈ S, ∃a⁻¹ ∈ S, a * a⁻¹ = e  
• 교환법칙: ∀a, b ∈ S, a * b = b * a

모츠킨 수열(Motzkin sequence)

0. 서론

카탈란 수열과 비슷하지만 또 재밌는 수열이 한가지 있습니다. 바로 모츠킨 수열(Motzkin numbers)인데요

오늘은 이 모츠킨 수열을 한번 살펴보도록 하겠습니다.

카탈란 수열에 +a한 수열이므로, 사실 카탈란 수열(https://omnil.tistory.com/221)시리즈를 전부 읽고 오시는 걸 추천드립니다.

1. 모츠킨 수열이란?

조합론에서 등장하는 아름다운 수열 중 하나가 모츠킨 수열(Motzkin numbers)입니다. 이 수열은 특정한 경로를 세는 문제나 괄호 구조, 평면 그래프의 엣지 수와도 관련이 있어, 카탈란 수열과 함께 종종 등장합니다.

카탈란 수열과 마찬가지로 테오도르 모츠킨(Theodore Motzkin)이 1948년 체계화해 발표한 것을 계기로 명명된 수열입니다.

2. 정의

모츠킨 수열 $M_n$은

1) 제일 간단하게 카탈란 수열(https://omnil.tistory.com/221)의 Dyck path에서 우상향(↗), 우하향(↘) 외에 평행이동(→)이 추가된 수열입니다.

2) 다음 조건을 만족하는 경로의 수로 정의됩니다:

시작점 $(0,0)$에서 시작하여 $(n,0)$에서 끝나는 경로 중,

1. 한 번에 $(1,1)$ (↗), $(1,0)$ (→), $(1,-1)$ (↘) 이동 가능하고
2. 절대 음의 높이(음수 y좌표)를 가지지 않는 경로의 개수.

즉, 위로 올라가거나 수평으로 가거나 내려가되, 절대로 수평선((0,0)~(n,0)) 아래로 내려가지 않는 경로의 개수를 셉니다.

3. 예시

$ M_0 = 1, \ M_1 = 1, \ M_2 = 2, \ M_3 = 4, \ M_4 = 9, \ M_5 = 21, \ M_6 = 51, \ \cdots $

카탈란 수보다 증가속도가 느리다고 생각할수도 있지만, 사실은 경우의 수가 한가지 더 늘어나서 더 빠르게 증가합니다.

그러나 항 수로 보면 느리게 증가하게 보이는 이유는, 카탈란 수와는 다르게 조건이 홀수개 이므로 수열 자체가 $ n \rightarrow 2n $으로 정의되던 카탈란 수열과 다르게 $ n \rightarrow n $으로 정의되기 때문입니다.

실제로 짝수항만 놓고보면 카탈란 수열보다 더 빠르게 증가함을 알 수 있습니다.

4. 점화식

모츠킨 수열을 다음과 같은 점화식을 만족합니다.

$ M_0 = 1, \ M_1 = 1, \ M_n = M_{n-1} + \sum \limits _{k=0} ^{n-2} M_kM_{n-2-k} \quad \operatorname{for} \ n \ge 2$

1) 첫 시작이 수평(→)이라면, 단순히 경로가 하나 줄어든 것이므로 $ M_{n-1} $ 값을 가집니다.

2) 첫 시작이 수평(→)이 아니라면, 무조건 우상향(↗)으로 시작해야하며, 이것은 카탈란 수의 점화식과 동일한 모양을 갖습니다.

단, 카탈란 수열은 무조건 총 경로가 짝수개여야만 하므로 점화식에서 -1만 빼 주어도 1쌍(시작:우상향, 끝:우하향)이 빠지는 결과가 나오지만, 모츠킨 수열은 총 경로가 홀수개여도 되므로, 점화식에서 -2(시작:우상향, 끝:우하향)를 빼주어야 합니다.

5. 생성함수

점화식을 알고있으니, 생성함수도 구할 수 있습니다.

카탈란 수열과 비슷하게 생성함수를 구해보면

$ M(x) = \sum \limits _{n=0} ^\infty M_n x^n = \frac{1-x-\sqrt{1-2x-3x^2}}{2x^2} $

으로 구해집니다만.. 카탈란 수보다 근호 안쪽이 한 차수 늘어난 걸 보면, 생성함수로 일반항 찾기는 아주 쉽지 않아보입니다.

일단 생성함수도 구할 수 있다 정도로만 생각하시고 넘어가시죠

사실 모츠킨수열은 조합론적 수열이다보니 경우의 수로 일반항 구하는게 더 쉽습니다.(카탈란 수열에서도 경우의 수로 구하는게 훨씬 쉬웠죠?)

6. 일반항

모츠킨 수열의 일반항은

$ M_n = \sum \limits_{k=0}^{[n/2]} \ _{n}\operatorname{C}_{2k} \ C_k$

여기서 왼쪽 C는 조합이고, 오른쪽 C는 카탈란 수 인데, 헛갈리니까 binomial 표현으로 바꿔주면

$ M_n = \sum \limits_{k=0}^{[n/2]} \binom{n}{2k} \ C_k$

이 됩니다.

여기서  
- $ \binom{n}{2k} $는 전체 n칸 중에 길이 2k짜리 구간을 선택하는 방법의 수를 나타내며,  
- $ C_k $는 카탈란 수로, 길이 2k인 Dyck path의 개수를 의미합니다.



이 식을 조합적으로 해석하면 다음과 같습니다.

1. 전체 경로의 길이는 n입니다.  
   우리는 이 길이를 Dyck path 구간(길이 2씩 짝을 이루는 구간)과 수평선(→)으로 나눠 생각합니다.

2. 짝수 영역 선택하기:  
   Dyck path는 길이가 항상 짝수여야 하므로, 2k ≤ n인 k에 대해서만 고려할 수 있습니다.  
   즉, 가능한 k의 범위는 0 ≤ k ≤ [n/2]입니다.(여기서 대괄호는 '가우스 기호'혹은 '가우스 함수'라고 불리며, '기호 안의 값을 넘지 않는 최대 정수'를 의미합니다. 내림(floor)과 동일합니다. 즉, [2.5] = 2입니다.)[여기서 이 기호는 짝수 2k가 전체 길이 n을 넘지 않게 제한하는 역할을 합니다.]

3. $ \binom{n}{2k} $는 길이 n 중에서 길이 2k짜리 블록이 들어가는 위치를 고르는 방법입니다.

4. $ C_k $는 선택된 2k칸에 대해 Dyck path를 구성하는 방법의 수입니다.

5. 남은 n - 2k칸은 모두 수평선(→)으로 채우면 됩니다.

즉,  
- 각 k마다  
  $ \binom{n}{2k} $: Dyck path가 들어갈 위치 조합 ×  
  $ C_k $: 그 위치에 Dyck path를 실제로 배치하는 방법  
을 곱해서 전체 경로의 수를 계산하는 것입니다.

예를 들어 n = 3이라면,  
가능한 k는 0 또는 1입니다.

- k = 0: 전부 수평선(→) → 1가지  
- k = 1:  
  $ \binom{3}{2} $ = 3 (길이 2짜리 블록 하나를 어디 넣을지 선택) ×  
  C₁ = 1  
  → 총 3가지

따라서,

$ M_3 = \binom{3}{0}·C_0 + \binom{3}{2}·C_1 = 1·1 + 3·1 = 4 $

다시 정리해보자면

$ M_n = \sum \limits_{k=0}^{[n/2]} \binom{n}{2k} \ C_k$

- k는 Dyck path로 채울 수 있는 짝수 영역의 개수  
- binom(n, 2k)는 그 위치를 고르는 조합  
- $ C_k $는 그 영역에 실제 Dyck path를 채우는 방법의 수

라는 조합적 해석을 갖습니다.

여기서 카탈란 수열 $ C_k $는 $ \frac{1}{k+1}\binom{2k}{k} $이므로 전체 풀어쓰면

$ M_n = \sum \limits_{k=0}^{[n/2]} \binom{n}{2k} \cdot \frac{1}{k+1}\binom{2k}{k}$

결국, 카탈란 수열을 나눠서 얘들이 어디에 쏙쏙 배치될지만 결정하는게 모츠킨 수열이네요~

7. 결론

모츠킨 수열의 점화식: $ M_0 = 1, \ M_1 = 1, \ M_n = M_{n-1} + \sum \limits _{k=0} ^{n-2} M_kM_{n-2-k} \quad \operatorname{for} \ n \ge 2$

모츠킨 수열의 일반항: $ M_n = \sum \limits_{k=0}^{[n/2]} \binom{n}{2k} \cdot \frac{1}{k+1}\binom{2k}{k}$

카탈란 수열을 심도있게 공부해봤다면, 너무나도 쉽게 카탈란 수가 들어갈 공간만 계산해주면 바로 모츠킨 수열의 일반항이 나온다는 사실을 알 수가 있답니다~

신입생의 꿈과 대학교 2학년의 꿈(Freshman's dream & Sophomore's dream)

0. 서론

과거 작성하였던 0에서 1사이의 x^x(x의 x승) 적분 값 계산(integral from 0 to 1 x to the power x dx) 포스팅이 있습니다.

고등학생 때 미적분을 공부하다 궁금했었는데, 결국 그 당시에 해결하지는 못하고 나중에 대학교를 졸업하고 나서야 우연히 해결방법을 접하고 신기한 마음에 포스팅을 올렸었죠.

그러나 그때까지도 이게 정확히 뭔지 몰랐다가, 요근래 정확한 명칭을 알게되었습니다.

바로 "대학교 2학년생의 꿈(Sophomore's dream)"이라는 이름이더군요.

수학자들이 붙인 이름입니다.

이걸 보면 모든 학문이 한번에 짠하고 완성되는 경우는 없는 것 같습니다.

뭔가 하나씩 하나씩 시간이 지나며 완성되는 느낌이랄까요?

그런데 왜 하필 "대학교 2학년생의 꿈(Sophomore's dream)"일까요?

"대학교 1학년생의 꿈(신입생의 꿈, Freshman's dream)"도 있을까요?

혹시 다른 "꿈" 시리즈들도 있을까요?

이 포스팅의 시작은 바로 여기서 부터입니다.

1. 신입생의 꿈 혹은 대학교 1학년생의 꿈(Freshman's dream)

1-1. 정의

대학교 1학년생의 꿈은 다음과 같습니다.

$ (x+y)^p = x^p + y^p $

1-2. 유래

사실 곱셈공식을 처음 배울 때 처음 실수하는 구간이죠.

$ 3(x+y) = 3x+3y $와 같이 분배법칙에 익숙했던 우리 모두가 한번쯤은 거쳐가지 않았을까요

그리고 한편으론 '이렇게 쉬웠으면 얼마나 좋아~'싶은 바람이기도 하죠.(왜 '바람'이냐면, 아시잖아요? 일반적인 상황에서 p가 1인 경우를 제외하고는 이항계수와 각 항의 곱의 조합으로 인하여 저렇게 심플하게 나올 수가 없답니다)

그래서 어떻게 보자면, 수학자들이 "초심자들의 실수를 장난스럽게 놀리기 위해 + 초심자들의 바람"을 담아서 이것을 신입생의 꿈(Freshman's dream)이라고 부르기 시작했습니다.

"전 세계적으로 곱셈공식은 대학교 입학 전에 배우는데 왜 '신입생'이냐"고 하신다면, 사실 처음 붙인 사람의 의도를 알지 못하는 한 정확하게 알 수는 없지만 유추해보자면

1. 대학교육의 '초심자'의 의미
2. 제대로 학문하는 사람(교수)이 처음 보는 학생
3. 이전까지는 '기본'적인 것들을 배웠다면 정말 대학교에서 본격적인 '수학'이라는 학문에 처음 들어온 뉴비

뭐 이정도의 느낌으로 신입생의 꿈 혹은 대학교1학년생의 꿈이라고 불렀겠죠?

대략 용어가 처음 등장한건 1940년대, 본격적으로 교재에까지 올라온 건 1974년이라고하니, 그렇게 엄청 오래된 용어는 아닙니다.

1-3. 그냥 헛소리일 뿐인가?

그러나 일반적으로는 성립하지 않는 저 식도 특수한 환경에서는 성립하게 됩니다.

아주 간단하게 설명해서, 특정 수가 p가 되면 0이 되는 공간에서 p가 소수일 때 저 등식은 성립합니다.

가령 p가 2가 되면 0이 되는 공간이 있다고 해봅시다.

0은 0이고, 1은 1이고, 2는 0입니다.

여기서 $ (x + y)^2 $은 $ x^2 + 2xy + y^2 $으로 전개되지만, 공간 정의에서 2는 0이 되므로 결국 $ x^2 + 0 + y^2 = x^2 + y^2 $이 됩니다.

따라서 신입생의 꿈이 성립하는거죠.

여기서부터는 좀더 나아가는 부분입니다. 가볍게 읽고 싶으시다면 건너 뛰셔도 좋습니다. 읽다가 복잡하시면 그냥 넘어가셔도 좋습니다.

2. 대학교 2학년생의 꿈(Shopomore's dream)

자, 그럼 대학교 2학년생의 꿈은 뭘까요?

2-1. 정의

$ \int^1_0 x^{-x} dx = \sum \limits _{n=1}^\infty \frac{1}{n^n} $

$ \int^1_0 x^x dx = \sum \limits _{n=1}^\infty \frac{(-1)^{n+1}}{n^n} = - \sum \limits _{n=1}^\infty (-n)^{-n} $

위의 두 식을 대학교 2학년의 꿈이라고 합니다.

그리고 위키피디아 등 여러 문헌에서 두 식을 1697년 요한 베르누이(Johann Bernoulli)가 발견했다고 저술하고 있습니다.

여담으로 요한 베르누이는, 우리에게 익숙한 '베르누이의 정리'를 발표한 다니엘 베르누이의 아버지 입니다.

2-2. 유래

그럼 진짜로 요한 베르누이는 이 두 식을 발표했을까요?

현재 문헌상에서 찾을 수 있는 것은 1742년에 총 4권으로 출간된 "Opera omnia"입니다.

Jean(Johann) Bernoulli가 그동안 저술한 것을 모아서 출간한 전집이죠.

그리고 여기서 Vol 3, pp 376-383에 "대학교 2학년의 꿈" 식의 증명이 등장합니다.

(원문은 구글 아카이브(https://archive.org/details/johannisbernoul00berngoog/page/n406/mode/1up)에서 확인하실 수 있습니다. 세상좋아졌어요.. 1742년 출간된 책을 인터넷으로 볼 수 있다니...)

1697년 악타 에루디토룸(Acta Eruditorum) 3월호에 실린 논문의 내용을 다시 정리하여 소개하고 있죠.

이 논문에서 요한 베르누이는 "지수함수 계산법의 원리(Principia calculi exponentialium)는 내가 처음 고안해낸 것으로, 이후 1697년 3월호 "Acta Eruditorum"에 발표했다"라고 밝히고 있습니다.

그리고 내용을 좀 더 살펴보면, 사실은 본인은 이 증명을 이미 예전에 발견하였으나 따로 알리지는 않고있었지만 라이프니츠 등 다른 수학자들이 요청하여 공개한다고 밝히고 있습니다.

그리고 뒤이어 나오는 증명은 $ \int_0^1 x^x dx $를 급수로 풀어내는 증명입니다.

우리는 이전 포스팅(https://omnil.tistory.com/173)에서 감마함수를 이용하여 식변형 만을 가지고 이를 풀었었는데요,

실제로 요한 베르누이는 이 적분을

1. 로그변환($ x^x = e^{x \cdot \ln x} $)
2. 매클로린 급수 전개
3. 항별 부분적분
4. x = 1 대입

의 방법으로 구하고 있습니다.(이후에는 일반항 $ x^n(\ln x)^m $에 대한 일반화된 적분 규칙을 정립하고, 논문을 마무리짓습니다.)

더불어, 이 식은 매우 빠르게 수렴하기 때문에 앞 몇 항만 계산해도 소수점 아래 10자리까지 계산할 수 있다고 밝혔습니다.

즉, 요한 베르누이의 논문에서는

$ \int^1_0 x^x dx = \sum \limits _{n=1}^\infty \frac{(-1)^{n+1}}{n^n} = - \sum \limits _{n=1}^\infty (-n)^{-n} $

이 식만 등장한다고 볼 수 있죠.

2-3. 검증

그렇다면, $ \int^1_0 x^{-x} dx = \sum \limits _{n=1}^\infty \frac{1}{n^n} $ 이 식은 어디서 나온걸까요? 후대에 다른 수학자가 임의로 넣은 걸까요?

사실 베르누이의 방식을 따르던, 저희가 구했던 방식을 따르던 첫 함수를 $ x^{-x} $로 놓고 풀면, 아주 간단하게 식이 유도됩니다.

따라서 베르누이가 발견했다고도 볼 수 있죠(베르누이가 이 함수를 적분할 수 있는 방법을 찾은거나 마찬가지니까요)

더불어 오히려 처음 구한 $ x^x $보다 그 식이 너무나도 깔끔하고 딱 보기에 좌항과 우항이 적분이냐 급수냐의 차이만 있을 뿐 식이 똑같기 때문에 놀라움을 자아낼 수 있죠.

$ \int^1_0 \frac{1}{x^{x}} dx = \sum \limits _{n=1}^\infty \frac{1}{n^n} $

그리고 이것을 바탕으로 대학교 2학년의 꿈(Sophormore's dream)이라는 언어유희가 탄생합니다.

첫 언급은 Borwein의 저술에 2004년에 등장하는 것으로 알려져 있습니다.

2-4. 신입생의 꿈 vs 대학교 2학년의 꿈

신입생의 꿈이라는 말은 위에서 '직관적으로 될 것 같지만 되지 않는 등식'을 일종의 '장난+그들의 염원'을 담아서 장난식으로 붙였다고 했습니다.

여기서 대학교 2학년의 꿈이라는 말은 반대로 '직관적으로 이게 돼!?' 싶은 등식이 '실제로 성립하는' 놀라움을 담아 붙인 셈입니다.

3. 다른 꿈 시리즈?

인터넷을 돌아다니다보면 '초등학생의 꿈'이니 뭐니 여러 '꿈'시리즈가 보이는 듯도 싶은데, 세계적으로 통용되는 보편적인 개념이나 용어는 아니고, 오히려 "'신입생의 꿈'처럼 어찌보면 '억지'인 상황을 제시하고, 어떤 특수한 상황에서는 성립한다는 것을 제시하는" 스타일입니다.

대표적으로 '초등학생의 꿈'은 과학잡지 등에서 기고로 실렸던 흔적을 찾을 수 있습니다.(뭐 사실 문제는 만들기 나름이지요. 신입생의 꿈 스타일이면 다 '~~꿈'이라고 할 수 있지 않을까요)

억지인 상황:

분수의 덧셈에서 통분을 하지않고, 분모끼리 분자끼리 더하는 상황(현실적으로는 성립하지 않지만, 직관적으로 '이렇게 해도 되지 않나!?'싶은 오류 상황)

특수한 해:

어떠한 집합 $ F_n $를 정의합시다.

이 집합은 0과 1사이의 기약분수의 모임입니다.

그리고 여기서 분모가 n 이하인 것들을 크기 순서대로 배열하기로 합시다.

수식으로 표현해보자면,

$ F_n = \left\{ \frac{a}{b} \,\middle|\, 0 \leq \frac{a}{b} \leq 1,\ \gcd(a,b) = 1,\ b \leq n \right\} $

이 됩니다. 여기서 gcd는 최대공약수(Greatest Common Divisor)로, 최대공약수가 1이라는 말은 두 수가 서로소(coprime)이라는 뜻이고 분수로 확장되면 기약분수를 나타내는 말이 되겠죠?

참고로 이 집합의 이름은 Farey set이라고 부른답니다.

예시로 볼까요?

• $ F_1 = \left\{ \frac{0}{1}, \frac{1}{1} \right\} $
• $ F_2 = \left\{\frac{0}{1}, \frac{1}{2}, \frac{1}{1} \right\} $
• $ F_3 = \left\{\frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1} \right\} $

그리고 이 집합의 연속된 세 수를 고르면, 첫항과 세번째항의 '초등학생의 꿈' 연산의 결과가 두번째 항이 되는 것을 알 수 있습니다.

4. 결론

역사적 시간으로 다시 정리해보자면,

1. 베르누이가 1697년에 $ \int^1_0 x^x dx = \sum \limits _{n=1}^\infty (-1)^{n+1}n^{-n} = - \sum \limits _{n=1}^\infty (-n)^{-n} $을 발견
2. 1940~70년대 신입생의 꿈이라는 말이 만들어짐(초심자의 실수+그들의 바람 을 표현한 용어(직관적으로 될 것 같은데 안된다))
3. 2004년 Borwein등의 저술에서 베르누이가 발견한 내용에 대학교 2학년생의 꿈이라는 용어를 붙임(신입생의 꿈과는 반대로 '직관적으로 맞는거 같은데... 맞는다!' 느낌)[여기서 원래 베르누이의 발견은 $ \int_0^1 x^x dx $이었지만, 약간 바꾸어서 더 아름다운 형태인 $ \int_0^1 x^{-x} dx $를 대표적인 식으로 표현(사실상 약간의 식변형이라 베르누이 논문에 직접 언급되지는 않지만 베르누이가 발견했다고해도 틀린말은 아님)]
4. 이후에 다른 '꿈'들이 있었지만, 세계적으로 통용되는 것들은 아님

이렇게 되겠네요

5. 마무리

어떻게 오늘 포스팅도 즐거우셨나요? 우리모두 꿈을 꿔보도록 합시다~

정규분포의 확률밀도함수(Probability Density Function, PDF) 증명

0. 서론

확률밀도함수(PDF), 그 중에서도 정규분포함수가 왜 너무나도 당연하게 유도되는지를 증명해보려고 합니다.

신기하게도 하나하나 따라가다보면, 우리가 아는 그 유명한 종 모양 그래프가 나온답니다.

1. 정규분포의 함수 모양은 어떻게 생겼나?

아시는 분들은 대충 종 모양이라고 알고 계시겠고, 더욱 자세히 아시는 분들은 적어도 이 함수가 e의 지수함수꼴이라는 것은 알고계실겁니다.

그러나 그게 왜 그렇게 나오는지는 모르시는 경우가 많을 것이라 생각됩니다. 그럼 정말 '무지'에서 시작해서 이 그래프를 찾아가보도록 하겠습니다.

2. 조건들을 확인하자

우리가 아는 정규분포의 pdf의 조건들은 다음과 같습니다.

1. $ \int_{-\infty}^\infty f(x) dx = 1 $ : 함수의 전체 넓이는 1(=전체 확률은 1)
2. $ \int_{-\infty}^\infty x \cdot f(x) dx = \mu $ : 확률변수 x의 기댓값은 평균($ \mu $)
3. $ \int_{-\infty}^\infty (x-\mu)^2 \cdot f(x) dx = \sigma^2 $ : 확률변수 x의 분산은 표준편차($ \sigma $)의 제곱
4. $ \mu $를 기준으로 좌우 대칭
5. 최대한 자연적인 분포(분포가 치우침이 없고 편향되지 않음)

이 조건들을 가지고 바로 함수의 모양을 찾아볼까요?

3. 최대한 자연적이다?

최대한 자연스러운 분포란 무엇일까요?

예를 들어, 동전을 던진다고 가정해봅시다.

가장 자연스러운 상황은 앞면이 나올 확률이 0.5, 뒷면도 0.5인 경우입니다.
왜냐하면 결과를 전혀 예측할 수 없기 때문이죠. (어느 쪽이 나올지 도무지 알 수 없음)

반면, 만약 앞면이 나올 확률이 0.99, 뒷면은 0.01이라면 어떨까요?
이건 거의 항상 앞면이 나오는 인위적인 상황으로, 결과를 예측하기 매우 쉽습니다.
더 이상 ‘무작위’라기보다는 ‘조작된’ 느낌이 들죠.

이처럼 우리가 말하는 ‘자연스러운 분포’란
결과를 예측하기 가장 어려운 상태,
즉 불확실성이 최대인 상태라고 할 수 있습니다.

그런데 생각해봅시다.

앞면이 나왔을 때 더 놀라운 경우는 어느 쪽일까요?

• 확률이 0.5인 공정한 동전?
• 아니면 0.99로 앞면이 나오는 조작된 동전?

당연히 전자입니다.

공정한 동전에서는 앞면과 뒷면이 동일한 가능성을 가지기 때문에,
결과가 나왔을 때 우리는 순간적으로 “아! 앞면이 나왔네!” 하고 반응하게 되죠.
반대로 조작된 동전에서는 앞면이 나와도 별로 새로울 것이 없습니다.
애초에 그럴 거라 거의 확신하고 있었으니까요.

이런 “놀라움의 크기”를 다른 말로 표현하면,
우리가 그 순간 “새롭게 알게 된 정보의 양”,
즉 정보량이라고 할 수 있습니다.

정리해보면 이렇게 연결됩니다:

불확실성이 크다 = 예측이 어렵다 = 놀라움이 크다 = 정보량이 크다

그리고 정보이론에서는 이것을 '엔트로피(entropy)'라고 부릅니다. 정보량이 크면 엔트로피가 큽니다.

[엔트로피의 원래 의미에서도 무질서도가 증가하는게 엔트로피가 크다고 하잖아요? 무질서할수록 우리가 알아야할 정보량은 커집니다.]

자, 그럼 정리되었습니다. 정규분포의 pdf는 엔트로피가 최대가 되어야 합니다.

4. 엔트로피는 어떻게 정의되는가

엔트로피는 샤논 엔트로피 공식(Shannon entropy formula)으로 구할 수 있습니다.

정보이론에서 샤논이라는 분이 엔트로피(불확실성)을 정량적으로 측정하기 위해 제안한 공식이죠.

수식을 보면

$ H(X) = - \sum p_i \log_b p_i $

이와 같습니다.

여기서 b가 2이면 bit로 나오고, e이면 nat, 10이면 hartley라고 하는데, 10은 거의 안쓰니까 크게 신경 안쓰셔도 됩니다.

p는 확률이죠.

이 수식은 정보이론에서 파생되었기 때문에 bit로 계산되는 이산적 공식이지만, 이 개념을 이용해서 연속적으로도 활용할 수 있습니다.

또한 보통 연속적으로 사용할때는 b가 e인 nat(natural unit of information) 단위로 쓰이지만, 이 단위가 크게 중요한 부분은 아닙니다.

중요한건 이 공식으로 연속함수의 불확실성을 나타낼 것이라는 점입니다.

$ H[f] = - \int f(x) \ln f(x) dx $

이제 이 공식에서 f(x)가 가장 불확실함을 나타내는 함수를 찾으면 됩니다. 그렇다면 H[f] 즉, 함수 f의 엔트로피가 최대가 되면 되겠죠?

5. 값이 최대가 아니라, 함수가 최대라구요?

여기서 값이 최대인 것을 찾는 방법이 미분법이라고 한다면, 함수가 최대인 것을 찾는 방법은 변분법이라고 불립니다.

그러면 바로 H[f]를 바로 변분법을 쓰면 될까요?

아니겠죠..? 위에서 조건들이 엄청 많았는데 그것들을 무시하고 찾으면 안되는 거잖아요?

그렇다면 위의 조건들을 어떻게 반영할 것이냐.. 하면 여기서 라그랑주 승수법이라는것이 나옵니다.

어떤 함수에 대해서 각 조건들에 라그랑주 승수를 곱해서 원 함수에서 더하거나 빼서 그 함수를 조건짓는 겁니다.

그렇게 해서 중간에 나오는 식을 '라그랑지안'이라고 부릅니다.

그렇다면 H[f]에서 각 조건들을 빼주면 되겠죠?

$ \mathcal{L} = - \int f(x) \ln f(x) dx - \lambda_0 ( \int f(x) dx -1 ) - \lambda_1 ( \int x \cdot f(x) dx - \mu ) - \lambda_2 ( \int (x-\mu)^2 \cdot f(x) dx - \sigma^2 ) $

이렇게 정리될겁니다.

그리고 여기에서 변분법을 적용하여(함수로 미분하는 겁니다) 이 값이 0인 점을 찾으면 미분처럼 극값을 주는 함수를 찾을 수 있습니다.

$ \frac{\delta \mathcal{L}}{\delta f(x)} = - (1 + \ln f(x)) - \lambda_0 - \lambda_1 \cdot x - \lambda_2 \cdot (x-\mu)^2 = 0 $

으로 나올테고, 이를 정리하면

$ \ln f(x) = -1 - \lambda_0 - \lambda_1 \cdot x - \lambda_2 \cdot (x-\mu)^2 $

이 되고, 이를 다시 f(x)로 표현하면

$ f(x) = e^{-1 - \lambda_0 - \lambda_1 \cdot x - \lambda_2 \cdot (x-\mu)^2} $

$ f(x) = Ae^{- \lambda_1 \cdot x - \lambda_2 \cdot (x-\mu)^2} $

이렇게 정리할 수 있습니다.

그리고 여기서 '함수는 평균을 기준으로 좌우 대칭이다'라는 조건에 의해 $ \lambda_1 $은 0이 되어야만 합니다. x가 살아있으면 이 함수는 좌우 대칭이 깨지기 때문이죠. 따라서 다시 써보면

$ f(x) = Ae^{- \lambda_2 \cdot (x-\mu)^2} $

이렇게 정리가 됩니다.

그리고 이것을 통해서 정말 신기하게도, 이 함수의 '개형'을 알게 되었습니다.

그러면 이제 $ \lambda_2 $와 A만 알면 완벽한 정규분포식을 알 수 있겠군요!?

6. $ \lambda_2 $와 A 찾으러 떠나세~

여기서 다시한번 정리해보죠. 정규분포함수의 pdf는 $ f(x) = Ae^{- \lambda_2 \cdot (x-\mu)^2} $입니다.

그렇다면,

조건1:

조건 $ \int_{-\infty}^\infty f(x) dx = 1 $에서, f(x)를 대입하면

$ \int_{-\infty}^\infty Ae^{- \lambda_2 \cdot (x-\mu)^2} dx =1  $

이렇게 정리가되고, 이것을 풀면 $ \lambda_2 $와 A를 구할 수 있겠네요.

일단, A는 상수계수이므로 적분기호 밖으로 뺄 수 있을테니, $ \lambda_2 $부터 구해보도록하죠.

$ A \int_{-\infty}^\infty e^{- \lambda_2 \cdot (x-\mu)^2} dx = 1 $

그러나 여기서 안타까운 상황에 직면합니다.

$ e^{x^2} $꼴의 적분은 자명한 원시함수가 없음이 밝혀져있죠.(리우빌의 정리(Liouville’s theorem on integration in finite terms)에 의해 증명됩니다.)

그러면 풀지 못하냐.. 하면 우리 엄청나신 가우스님께서 이걸 약간의 트릭으로 아주 멋지게 풀어내십니다.

일단 $ x-\mu $를 $ u $로 치환해줍니다.

$ \int _{-\infty}^\infty e^{-\lambda_2 u^2} du $

여기서 해를 $ I $라고 하면 식은 다시

$ I = \int _{-\infty}^\infty e^{-\lambda_2 u^2} du $

이렇게 쓸 수 있습니다.

그리고 여기서 양변을 제곱해줍니다.

적분 변수를 구분해주기위해 다른 문자인 x, y를 씁니다. 여기서 x는 위에서의 x와 상관이 없습니다.(잠깐 쓰고 사라질 친구들이라 그냥 x쓰겠습니다)

$ I^2 = \left( \int _{-\infty}^\infty e^{-\lambda_2 x^2} dx \right)\left( \int _{-\infty}^\infty e^{-\lambda_2 y^2} dy \right) $

적분을 합치고, 수식을 정리하면

$ I^2 = \iint _{\mathbb{R^2}} e^{-\lambda_2 (x^2+y^2)} dx dy $

여기서 $ \mathbb{R^2} $는 '실수*실수 모든 영역에서'라는 뜻으로 $ \int _{-\infty}^\infty\int _{-\infty}^\infty = \iint_{\mathbb{R^2}} $입니다.

여기서 $ x^2+y^2 = r^2 $이라는, 원의 방정식이자 극좌표 표기 형식으로 바꿔보면,

$ dx dy $의 경우 미소 면적을 뜻하는 것인데, 극좌표 형식에서는 미소한 $ \theta $에 대해 부채꼴의 호의 길이인 $ rd\theta $와 $ dr$의 곱으로 표현할 수 있으므로 둘이 치환되며,

구간의 경우 $ r $이 0부터 무한대까지, 그리고 $ \theta $가 0에서 $2\pi$까지면 실수영역에서 $ \mathbb{R^2} $를 커버하므로 이와같이 치환하면 수식은

$ I^2 = \int_{0}^{2\pi}\int _{0}^\infty e^{-\lambda_2 r^2} rdrd\theta $

이와같이 바뀝니다.

여기서 안쪽 적분인

$\int _{0}^\infty e^{-\lambda_2 r^2} rdr$

부터 적분하면, $ \lambda_2 r^2 = v $,  $ 2\lambda_2 rdr = dv \Leftrightarrow rdr = \frac{dv}{2\lambda_2} $로 치환하면

$\frac{1}{2\lambda_2}\int_0^\infty e^{-v} dv $

이렇게 변형이 되고, $ \int_0^\infty e^{-v} dv = 1 $이므로

안쪽적분은 $\frac{1}{2\lambda_2}$가 나옵니다.

이제 바깥쪽 적분으로 들어가면

$ \frac{1}{2\lambda_2} \int_0^{2\pi}d\theta $이므로

$ I^2 = \frac{2\pi}{2\lambda_2} $

$ I = \sqrt{\frac{\pi}{\lambda_2}} $

가 됩니다.

$ A \int_{-\infty}^\infty e^{- \lambda_2 \cdot (x-\mu)^2} dx = 1 $

여기에서 적분부분이 $ I $이므로, $ A\sqrt{\frac{\pi}{\lambda_2}} = 1 $

$ A = \sqrt{\frac{\lambda_2}{\pi}} $

조건2:

여기서 저희는 분산조건도 만족시켜야 합니다.

$ \int_{-\infty}^\infty (x-\mu)^2 \cdot f(x) dx = \sigma^2 $

f(x)에 $ Ae^{- \lambda_2 \cdot (x-\mu)^2} $대입하고, 마찬가지로 $ x-\mu $를 $u$로 치환하면

$ \int_{-\infty}^\infty u^2 \cdot Ae^{- \lambda_2 \cdot u^2} du = \sigma^2 $

여기서 A를 적분 밖으로 빼면

$ A \int_{-\infty}^\infty u^2 \cdot e^{- \lambda_2 \cdot u^2} du = \sigma^2 $

요런식이 나오는데, 여기서 부분적분해야하나?라는 생각이 들수도 있지만, 아주 멋있는 해법이 있습니다.

아까

$ I = \int _{-\infty}^\infty e^{-\lambda_2 u^2} du = \sqrt{\frac{\pi}{\lambda_2}} $

였죠?

이걸 바로 $ \lambda_2 $로 미분해줍니다.

$ \frac{dI}{d\lambda_2} = \frac{d}{d\lambda_2}\int _{-\infty}^\infty e^{-\lambda_2 u^2} du = \int _{-\infty}^\infty \frac{d}{d\lambda_2}e^{-\lambda_2 u^2} du = \int_{-\infty}^\infty (-u^2) \cdot e^{- \lambda_2 \cdot u^2} du $

따라서

$ \int_{-\infty}^\infty u^2 \cdot e^{- \lambda_2 \cdot u^2} du = -\frac{d}{d\lambda_2}\sqrt{\frac{\pi}{\lambda_2}} $

$ = -\sqrt{\pi} \frac{d}{d\lambda_2} \lambda_2^{-\frac{1}{2}} $

$ = -\sqrt{\pi} (-\frac{1}{2}) \lambda_2^{-\frac{3}{2}} $

$ = \frac{1}{2}\sqrt{\frac{\pi}{\lambda_2^3}} $

$ = \frac{1}{2\lambda_2}\sqrt{\frac{\pi}{\lambda_2}} $

다시정리하면,

$ A \frac{1}{2\lambda_2}\sqrt{\frac{\pi}{\lambda_2}} = \sigma^2 $

위에서 $ A = \sqrt{\frac{\lambda_2}{\pi}} $이었으므로

$ \sqrt{\frac{\lambda_2}{\pi}} \frac{1}{2\lambda_2}\sqrt{\frac{\pi}{\lambda_2}} = \sigma^2 $

$ \frac{1}{2\lambda_2} = \sigma^2 $

$ \lambda_2 = \frac{1}{2\sigma^2} $

이렇게 $ \lambda_2 $가 구해지고, A는

$ A = \sqrt{\frac{\lambda_2}{\pi}} $

이므로 여기에 대입하면

$ A = \sqrt{\frac{1}{2\pi\sigma^2}} $

$ = \frac{1}{\sqrt{2\pi\sigma^2}} $

7. 결론

따라서 유도된 정규분포 pdf는

$ f(x) = \frac{1}{\sqrt{2\pi\sigma^2}}e^{- \frac{(x-\mu)^2}{2\sigma^2}} $

이와 같습니다.

완전 무에서부터 조건들만 가지고 정규분포 pdf가 증명되는게 너무 신기하지 않나요?

생성함수(Generating Function)란?(feat. 멱급수(power series))

0. 서론

생성함수(Generating function)에 대해 그 의미가 생소한 분들이 많은 것 같아 추가로 이 포스팅을 기획하였습니다.

이전까지 글들이 좀 더 수학적으로 엄밀하고, 수식을 통해서 논지가 진행되었던 것에서 이번 포스팅은 조금 탈피해보려고 합니다.

아무래도 개념적인 부분을 다루고, 심지어 생소한 개념이다보니 최대한 쉽게 써보려고 하는데요.

여기서 예시로 들거나 대화를 하는 듯한 부분은 하나의 과장이자 허구이니 진지하게 받아들이시지는 마시고, '아~ 그냥 이래서 이렇게 되었던 거구나~'정도로만 이해해주시면 감사하겠습니다.(진짜 저런 대담이 오갔다거나 저게 진짜 기원이라고 믿으시면 안됩니다... 흐름만 봐주세요..)

그럼 시작해보겠습니다.

1. '등비수열의 합' 공식을 아시나요?

혹시 '등비수열의 합' 혹은 '등비급수' 공식을 알고 계신가요?

고등학교에서 처음 나오는 부분이라, 고등학교 교육을 지나쳐 오신 분들은 조금 친숙하시거나 적어도 '아.. 그런것도 있긴했었다...' 하실테고 아직 고등학교 교육을 이수하지 못하신 분들이라면 '엥?'이라고 하실수도 있으실 겁니다.

결론적으로 공식만 써보면 다음과 같습니다.

$ \sum \limits _{n=0}^{\infty} ar^n = \frac{a}{1-r} $

여기서 a는 초항(제일 처음 항), r은 공비 죠.

그리고 여기서 r은 $ | r | < 1 $입니다. 이래야만 수렴하거든요.(간단히 쓰기로 했으니까 자세한 내용은 생략하겠습니다만, 부분합 공식에서 극한을 취해보면 $ | r | < 1 $인 경우에만 수렴한답니다.)

1-1. 등비급수 공식을 직접 유도해보자~

이 공식은 고등학교에서 두가지 방식으로 유도합니다.

1) 등비 수열의 부분합 공식에서 n에 극한을 취해서 구한다.

2) r을 하나 곱해서 빼서 구한다.

여기서 두번째 구하는 방법을 한번 볼까요?

먼저 어떤 등비수열의 무한급수가 있다고 해 봅시다. 그리고 이 친구를 그냥 $ S $라고 놓을께요.

편의상 초항 a는 1로 놓겠습니다.

$ \sum \limits _{n=0}^{\infty} r^n = \sum \limits _{n=0}^{\infty} r^n = 1 + r + r^2 + \cdots = S $

그리고 여기서 $ S $에 $ r $을 하나 곱해봅시다.

$ r+r^2+r^3+\cdots = rS $

오 근데 위 식과 아래 식을 잘 보면 항이 서로 뺄 수 있을 것 같이 생기지 않았나요? 바로 빼봅시다

$ 1 + r + r^2 + \cdots - (r+r^2+r^3+\cdots) = 1 = S - rS $

$ 1= S-rS \Leftrightarrow 1 = (1-r)S $

다시정리하면,

$ \frac{1}{1-r} = S \Leftrightarrow \frac{1}{1-r} = 1 + r + r^2 + \cdots $

여기서 초항 a를 편의상 1로 놓고 계산했지만, 다시 살려줘서 양변에 곱해주면

$ \frac{a}{1-r} = a(1 + r + r^2 + \cdots) = a \sum \limits _{n=0}^{\infty} r^n = \sum \limits _{n=0}^{\infty} ar^n $

바로 우리가 처음 보았던 바로 등비수열의 합 공식이 짜란 하고 펼쳐집니다.

1-2. 근데 이걸 다시 곱해보면?

근데, 이 수식에서 분모를 다시 양변 곱해볼 생각 해보신분 계신가요?

$ \frac{1}{1-r} = 1 + r + r^2 + \cdots $

바로 이부분에서요.

'무한한데 어떻게 분배하냐~~~'라고 하실수도 있지만, 잘 보면 분배는 (1-r)에서 1곱한 급수 - r곱한 급수가 된답니다.

$ (1+r+r^2+\cdots)(1-r) = (1+r+r^2+\cdots) - r(1+r+r^2+\cdots) = (1+r+r^2+\cdots) - (r+r^2+r^3+\cdots) $

이렇게 분배가 되구요.. 수식을 잘 보고 뺄셈을 해보시면... 1만 남는걸 알 수 있습니다.

(여기서 '빼는 항 개수가 안맞잖아요~'라고 하신 당신은 엄청난 재능러! 그러나 무한의 공간에서는 말 그대로 '무한'하기 때문에 항 수에 대한 1:1 매칭이 의미가 없답니다! 관심있는 분들은 '힐베르트 호텔'을 한번 찾아보세요!)

그럼 수식을 다시 써보면

$ \frac{1}{1-r} = 1+r+r^2+\cdots \Leftrightarrow 1 = (1+r+r^2+\cdots)(1-r) = 1 $

엥? $ 1 = 1 $이라는 너무나도 기묘한? 이상한? 결과가 나왔네요?

뭐 별거 없습니다. 그냥 '당연하다~'이소립니다.

"좌변이 1이고, 우변도 계산하면 1이니까 둘은 같잖아! 그러니까 너의 식변형은 맞아~"

라고 알려주는거나 마찬가지지요.

결국 저 무한한 등비 수열이 더하기로 연결되어있는 걸 '단 하나의 수식'으로 표현할 수 있다는 거죠!

그럼 이 당연한걸 왜 해봤냐면요...

2. r을 확장해보자~

이제 수학자들이 이런 생각을 하기 시작합니다.

"오호 신기한지고... 어떻게 무한한 더하기를 이 단 하나의 공식으로 표현할 수 있는겐가..."

"오호오호 너무나 신기한지고... 아니 그러면 '값'을 넣으면 '값'이 나오는 r이라는 '공비' 대신에 의문스러운 '무언가'를 나타내는 문자 x를 써보면 어떠할까?"

그렇게 문자 x로 확장을 해봤는데? 어머어머 이게 x라도 딱 맞는거에요~~ 1=1이 나와버렸다니까요~~ (궁금하시면 직접 x로 바꿔서 풀어보셔도 됩니다만.. 어차피 r이나 x나... 글자만 바뀐거니까 결과도 동일하겠죠...?)

3. x에다가 무슨 장난을 칠 수 있을까... 계수?

거기다 이게 "아니 공비(r)라고 하는 틀에 갖혀서는 무조건 공비의 조건을 만족해야만 수식이 수렴하면서 값이 나왔기에 그냥 그런갑다~~ 했는데, 이걸 x라고 놔버리고보니 우항이 x의 거듭제곱꼴이되면서 x의 계수가 다시 또 어떤 등비수열을 나타낼 수 있잖아!? 오마나 세상에나 만상에나!!"

"봐봐, 봐봐, x라고 하는 자리에 2x를 넣으면, x의 계수가 바로 공비가 2인 수열이 만들어진다니까!?"

아주 난리가 납니다. 완전히 새로운 접근이 되어버린거죠.

이제 무한한 수열을 단 하나의 수식으로 '압축'해서 표현할 수 있는 방법이 생긴겁니다. 혁신이었죠.

그리고 여기서 다시 잘 살펴보면 x는 '어떤 미지의 수'를 뜻하는게 아니라 진짜 말그대로 '그냥 무언가'를 뜻하는 걸로 출발해서 이와같은 결실을 맺었기에, 그리고 그 '그냥 무언가'를 몇 제곱 했는지가 바로 그 계수를 몇제곱했는지랑 같은 의미가 되며, 그냥 'n번째'를 나타내는 '$ x^n $'으로의 의미가 생기게 됩니다.

4. 계수가 할말이 있대~~ 집중~~

근데 여기서 수학자들이 또 아주 재밌는 사실을 발견합니다.

"근데, 꼭 등비수열만 이렇게 나타낼 수 있는걸까?"

그러면서 계수를 이제부터 (등비수열의 정의 $ a_n = ar^n $에서)

$ ar^n $으로 보지 않고 $ a_n $으로 봐버리는 겁니다. 발상의 전환! 집중과 선택!

그러면 바로 이 급수 비스므리한 수식은! 안타깝게도 등식이 깨져버립니다.

좌변의 수식이 바로 '등비급수'를 나타내는 수식이었기 때문이죠...

그러나 하늘이 무너져도 솟아날 구멍은 있다! 어떤 수학자가 발상의 전환을 해버립니다

"어? 그럼 그냥 좌변을 '나도 모르는 수식 무언가😵‍💫'라고 놓아버리면 우변도 바꿔도 되지 않을까?

아니 그러면... 반대로 생각해보면...

우변의 계수가 등비수열이었으니까 -> 좌변의 수식이 등비수열을 나타내는 수식

그렇다면

우변의 계수가 'ㅁㄴㅇㄹ'수열이면 -> 좌변의 수식이 'ㅁㄴㅇㄹ'수열을 나타내는 수식(일명 '나도 모르는 수식 무언가😵‍💫')

이 되어버리는 거네!?

그러면 이번엔 좌변이 '수식 무언가'니까 대애충 '수식이에요'하는 모냥으로 함수처럼 A(x) 이런식으로 써놓고, 우변의 계수에 내가 알고싶은 수식의 일반항 넣고 계산해서 계산이 되어버리면, 그 계산된게 '수식무언가'겠네!?!?!?!?

오 마이 갓!!"

이렇게 깨달음을 얻은 그들... 다시한번 심호흡하며 그동안 깨달은걸 다시한번 검토해봅니다.

1) 등비급수를 구하는 공식을 찾았다!

2) 거기에다가 공비대신에 문자 써도 성립하던데?

3) 어? 근데 문자 옆에 계수 쓰면 그 계수를 공비로 가지는 등비수열이 나와

4) 지금 이건 등비급수 공식을 가지고 계수가 등비수열을 나타내는걸 만들어낸거나 마찬가지네?

5) 여기서 등비수열을 또 일반항 $ a_n $으로도 표현할 수 있잖아?

6) 그렇다면 일반항 $ a_n $에 대해서 표시가 된다면, 아무 수열이나 다 쓸수있는거아냐?

7) 어? 그럼 '나도모르는 공식' 무언가는 계수가 'ㅁㄴㅇㄹ'수열을 나타낼 수도 있지 않을까?

8) 6번 7번을 섞어서 생각해보면, 'ㅁㄴㅇㄹ'수열을 넣고 계산해서 어떤 특정한 공식이 나온다면 그게 바로 그 수열의 '공식'이네!?

9) 반대로 이 공식을 $ a_n $으로 표시할 수 있으면, 이게 바로 그 수열의 일반항이 되는건가아아아아아아!!!!

한번 더 검토하고는 '유레카!'를 외치며, 그들은 자신들이 맞았음을 확신하고는 이내 계수에 온갖 수열을 다 넣어봅니다.

가장 간단한 등차수열도 넣어봅니다.

등차수열의 일반항은 다음과 같습니다.

$ a_n = a + (n-1)d \quad (n \ge 1) $

보통은 수열의 첫 항을 1항이라고 표시해서 이런 식이 나오는데, 그냥 첫 항을 0이라고 놔버리면 수식은 좀 더 간단해집니다.

$ a_n = a + nd \quad (n \ge 0) $

아까 우항을 아래와 같이 표기할 수 있다고 그랬습니다.

$ \sum\limits_{n=0}^{\infty} a_n x^n $

여기다 등차수열의 일반항을 대입해보면

$ \sum\limits_{n=0}^{\infty} \left(a + nd\right) x^n $

이렇게 될 겁니다.

근데 여기서 이 친구는 우항이었죠?

좌항은 '분명히 무슨 공식이 있을텐데...?'수준입니다. 그래서 그냥 '수식 비스므리한 무언가'라고 $ A(x) $라고 써주겠습니다.

그렇다면 완성된 수식은

$ A(x) = \sum\limits_{n=0}^{\infty} \left(a + nd\right) x^n $

사실상 급수수식

$ \frac{1}{1-rx} = \sum\limits_{n=0}^{\infty} r^n x^n $

과 다를바가 없습니다.(수식의 비슷한 정도를 위해 문자 x로 바꾼 버전으로 썼습니다)

다른점이라면 등비수열 수식은 이미 우리가 등비급수 수식을 통해 유도해 내려오면서 좌변을 알 뿐이고, 등차수열은 좌변을 모르니까 A(x)라고 놨을 뿐이죠.

개념 포스팅이니 자세한 유도는 생략하겠습니다만, 결국 풀어보면

$ A(x) = \frac{a}{1 - x} + \frac{d\,x}{(1 - x)^2} $

이렇게 됩니다. 결론은 '우리가 뭔지 몰라서 A(x)로 놨던 수식은 사실은 $ \frac{a}{1 - x} + \frac{d\,x}{(1 - x)^2} $ 였어~'

라는 뜻입니다.

그리고 이걸

$ \frac{1}{1-rx} = \sum\limits_{n=0}^{\infty} r^n x^n $

요런식으로 표현해보면

$ \frac{a}{1 - x} + \frac{d\,x}{(1 - x)^2} = \sum\limits_{n=0}^{\infty} \left(a + nd\right) x^n $

즉, 등차수열을 계수로 가지는 급수는 좌항과 같은 '단 하나의 수식'으로 표현 가능하대요~ 라는 의미가 되죠.

어머 이게 풀려버렸습니다. 등차수열이 또 단 하나의 수식으로 표현되어버립니다.

"와 미쳤다. 우효~ 이거 우리가 어마어마한걸 발견해버린거 아니냐고~~😱🔍"

수학자들은 신이났습니다.

그리곤 진짜 별의 별 수열들을 다 넣어보는데.... 어머나.. 모두다 단 하나의 수식으로 압축이 되어버리는거있죠~~~

이렇게 수열을 하나의 수식으로 다 표현할 수 있게 되자, 수학자들은 이 놀라운 방식을 아예 이름을 붙이기로 합니다.

거기다 왠지 '거창한 이름'을 지어주고 싶어졌죠.

5. 너의 이름은 생성함수니라~

그래서 이름도 아주 거창하게 '생성함수(generating function)'라고 지어버립니다.

처음 듣는 사람 아주 기죽게말이죠..

그러나 실상은 별거없어요.

• '생성' : 아 이걸로 무한한 수열을 만들어 낼 수(생성할 수) 있어~
• '함수' : 아 수식 비스므리한거니까 함수야~ 그리고 우항이 x의 거듭제곱으로 표현되어버려서 미적분이나 덧셈, 뺄셈, 곱셈, 나눗셈 등등 함수처럼 다룰 수 있어~ 그러니까 좌항 너는 이제부터 함수여~

라서 그냥 생성함수입니다.

그리고 좌항에 하나의 수식으로 표현되는 부분은 생성함수라고 이름 붙여줬으니, 우항에 x의 거듭제곱이 덧셈으로 연결되어있는 이 부분을 "그래 너네는 거듭제곱이 계속 더해지니까 '거듭제곱 급수' 혹은 거듭제곱이 계속 나오니까 power(거듭제곱) series(나열)라고 불러주마"라고 해버렸습니다. 한자로 거듭제곱이 '멱'이라서 멱급수라고도 하죠.

6. 모일 모처에서는...

동시에 다른곳에서는 다른 수학자들이 다른 고민을 하고 있었습니다.

"'초월함수(transcendental function)'가 너무 어려워!!! 크악!!!"

여기서 초월함수란, '유한한' 다항식의 합으로 표현가능한 대수적 함수를 '초월(transcendental)'했다는 뜻에서 붙인 함수에요. 말 그대로 $ e^x $, sin x, ln x 등을 말하는 거죠.

수학자들은 이 초월함수를 어떻게든 대수적 함수(유한 개의 다항식의 합으로 나타낼 수 있는 함수)로 나타내보려했으나 모두 실패했답니다... 그리고는 '초월함수'란 이름을 붙이고 백기를 들...려고 했으나! 일부 수학자가 이를 벅벅 갈면서

"너가 초월함수면 다야? 너가 어디 다항함수로 '근사'까지 할 수 없나 보자!"

라며 이 초월함수를 다항식으로 비슷하게 만들어보려고 애씁니다.

그리고 결국 '무한한' 다항식의 합. 바로 급수로 이 초월함수를 근사해 내는데 마침내 성공합니다.(테일러 급수(Taylor series), 매클로린 급수(Maclaurin series) 등)

정말 집념이 대단합니다.

그런데, 이 급수... 잘 보면 '무한한 다항식의 합' 즉, x의 거듭제곱의 합으로 표현이 됩니다. 그래서 이 수학자들은 여기에 '멱급수(power series)'라고 이름을 붙였죠. 영어 그대로 보자면 power 힘!이 아니라 거듭제곱!의 series 연속 이란 뜻이죠.

그런데 이거.... 어디서 본거 같지 않나요?

7. 대충돌

네, '수열의 압축법' 즉, 생성함수를 찾아낸 쪽도 x의 거듭제곱의 합으로 수열을 나타내고, 초월함수를 근사하는 방법을 찾아낸 쪽도 x의 거듭제곱의 합으로 함수를 근사합니다.

이제 이 둘이 옥신각신 싸웁니다.

누가 먼저냐...는건 관심도 없고, 이거 용어를 뭐라할지 싸웁니다.

서로 같은 용어를 쓰면 이게 생성함수에서 사용하는건지, 함수근사에서 사용하는건지 헛갈리잖아요?

그래서 결국 우여곡절 끝에 양측이 합의를 합니다.

초월함수측: 잘 보니까 우리 x의 사용법에 차이가 있는 것 같다. 우리는 x에 실제 값을 대입해서 함수처럼 쓴다. 그러니까 초월함수를 근사할 수 있지.

생성함수측: 그래 맞아. 우리는 x를 그냥 '문자'이자 그 거듭제곱이 '몇 번째인지'를 알려주는 색인으로만 쓰지 직접 값을 대입하지 않는다. 그러면 너네들이 진짜 값을 대입하니까 '멱급수(power series)'는 니네가 가져라.

초월함수측: 먼저 그렇게 선뜻 내주다니 고마운걸? 그럼 우리는 더 멋있는 이름을 지어주마. 아주 엘레강스하고 포멀하게~ 너네는 x를 실제 값으로 안쓰고 '형식적'으로 쓰니까 형식적 멱급수(formal power series)라고 붙여주마

생성함수측: 오우 왕년에 이름 쫌 지어보셨나봐?

양측: 호호호 오호호

뭐 실제로 이랬는지는 알 수 없지만... 어찌됐든 이러한 이유로 생성함수에서 사용하는 멱급수는 형식적 멱급수, 즉 x 자체에 특정 값을 대입하는 해석적 방식이 아닌 그냥 자리만 표기해주는 형식적 방식이 된 것입니다.

8. 결론

그래서 생성함수란 무엇이냐 하면,

1) 무한한 수열을 단 하나의 수식으로 압축시킨 것
2) 그러나 여기서 x는 형식적(색인같은)일 뿐 어떤 값을 가지진 않는다.

요 두가지로 표현할 수 있겠습니다. 

9. 더 나아가기

여기서 위에서 살짝 언급이 되었던 부분이 있습니다.

"일반항을 넣고 계산해서 생성함수를 알 수 있었으면, 반대로 생성함수를 알면 일반항을 알 수 있겠네?"

라는 구절이 있었죠.(뭐 물론 토시하나 안틀리고 저렇게 나오진 않았습니다만..)

네, 바로 이부분이 "계수추출"이라고 불리는 부분인데...

보통 수열은 처음부터 일반항이 정의가 되는데, 처음부터 일반항이 정의되지 않은 수열 이를테면 점화식으로만 정의되는 수열 같은 경우에많이 쓰는 개념입니다.

위에서 따라 내려왔던 일반항->생성함수 보다는, 생성함수->일반항(계수추출)을 주로 쓰게 되는데요.

1) 점화식으로 정의된 수열을 멱급수로 나타내고(우항의 형식으로 표현하고) 이를 계산해서 생성함수를 알아냅니다.

2) 그리고 그 생성함수를 가지고 반대로 일반항을 찾아냅니다.

즉, [점화식->멱급수의 계수로 대입(우항 스타일)->생성함수 찾아내기(우항으로 좌항 스타일 찾기)->일반항 찾아내기(계수추출:생성함수에서 일반항 찾기)]의 구조를 가진답니다.

결국 생성함수로 '압축!'했다가 '변형풀기!'한거죠.

10. 마무리

결국 생성함수는 수학자들이 수열을 다루는 방식에 큰 전환을 가져온 도구입니다.

무한한 수열을 단 하나의 수식으로 압축할 수 있다는 것만으로도 놀랍지만, 그 수식을 조작함으로써 일반항을 찾아내고 점화식을 해석할 수 있다는 점은 더욱 강력하죠.

이제 우리는 단순히 수열을 나열하는 것이 아니라, 수열을 '다룰 수 있는' 시대에 들어선 것입니다.

어떻게 최대한 수식사용을 지양하고 개념설명에 충실하려 노력했습니다만... 조금 이해가 되셨을지 모르겠습니다.

뭐라고 끝내야하지... 우리존재 화이팅요!💪📚

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

📘 카탈란 수열 시리즈

• 🌱 카탈란(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)까지 소개시켜드리도록 하겠습니다!

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

다음에 보아요!