생성함수

수열을 점화식으로 표현할 수도 있지만, 생성함수(generating function)라는 다항식을 이용해서 표현하는 방법도 있다고 한다.

뭔가 싶었다. 그런데, 좀 생각을 해 보니, 소수표현과 분수에 비유해서 설명할 수 있지 않을까 하는 생각이 들었다.

그러니까, 3/7 이라는 소수는 0부터 9까지의 수만 갖는 무한수열을 표현한다. 0.428571428571... 을 4, 2, 8, 5, 7, 1... 이렇게 이어지는 무한수열을 나타내는 것이라고 보자는 거다. 그럼, 좀 복잡한 점화식 대신에, 3/7 이라는 간단한 수로 무한한 수열을 표현할 수 있다.

그런데, 정수의 소수표현은 0부터 9까지의 수만 수열의 한 항으로 가질 수 있다는 한계가 있다. 이건 진법을 바꾸면 무한하게 늘어날 수 있겠지만, 아무리 진법을 바꾼데도 무한하게 증가하는 무한수열을 표현하는 경우는 표현할 수 없기 때문에, 비슷하고 좀 더 일반적인 무언가를 찾은 것이 다항식일 게다.

생성함수의 정의는 수열 {a_i}가 있을 때, sum_{i=0 .. inf} a_i x^i , 로 정의된다. 이 정의만 놓고 보면, 괜히 왜 복잡하게 x^n을 더 써서 복잡하게 만드나 하는 생각이 들지만, 이것의 묘미는, 이 무한 다항식을 간단한 다항식의 역수, 또는 간단한 분수다항식으로 표현할 수 있다는 것이다.

실제로, 위에 든 3/7 이라는 예는 x에 1/10을 집어넣을 것이 불과하다. 그 때의 무한급수는 다시금 3/7이 될 것이다.

생성함수가 무엇인가 고민하다, 아, 이런 것 아닐까란 생각이 불현듯 들어서 쓴 것이라, 엄밀하지 못하고. 정리되지 못했다. 틀리게 설명한 부분이 있다면 태클 걸어주기 바란다.