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

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

 

1. 서론

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

2. 생성함수?

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

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

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

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

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

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

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

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

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

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

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

이렇게 정리가 되겠죠?

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

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

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

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

로 표현할 수 있겠습니다.

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

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

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

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

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

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

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

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

이렇게 나올겁니다.

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

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

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

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

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

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

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

그럼 다시쓰면

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

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

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



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

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

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

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

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

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

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

이렇게 나오겠죠?

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

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

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

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

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

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

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

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

가 되겠네요.

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

식으로 쓰면

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

마찬가지로 정리해보면

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

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

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

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

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

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

이렇게 정리되겠습니다.

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

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

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

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

$ C(0) = C_0 = 1 $

입니다.

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

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

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

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

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

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

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

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

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

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

똑같이 극한을 취해주면

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

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

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

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

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

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

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

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

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

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

$ C(0) = 1 $

5. 결론

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

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

이것이었습니다!!!!

 

 

6. 여담

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