생성함수 (Generating Function)
쉽게 풀면
피보나치 수열(1, 1, 2, 3, 5, 8, ...)처럼 항들 사이에 규칙적인 관계가 있는 수열이 있다고 해봅시다. 이 수열의 각 항을 그대로 나열하는 대신, x, x², x³, ... 앞에 붙는 계수로 삼아 f(x) = 1 + 1·x + 2x² + 3x³ + 5x⁴ + ... 같은 하나의 함수(급수)로 압축해버리는 것이 생성함수의 아이디어입니다. 이렇게 수열을 함수 하나로 "포장"해두면, 수열 사이의 복잡한 점화 관계를 함수의 덧셈·곱셈 같은 대수적 계산으로 바꿔 풀 수 있습니다. 마치 여러 개의 숫자 목록을 다루기보다, 그 목록을 표현하는 함수 하나만 다루는 게 훨씬 편리한 것과 비슷합니다.
왜 중요한가
생성함수는 수열이나 조합적 대상을 직접 세는 대신 함수의 대수적 조작으로 바꾸어 다룰 수 있게 해주기 때문에, 조합론에서 어떤 구조의 개수를 세는 문제를 푸는 핵심 기법으로 쓰입니다. 알고리즘의 실행 시간을 나타내는 점화식을 분석하거나, 그래프의 부분구조를 세는 문제 등에서도 생성함수를 통해 닫힌 형태의 해를 얻는 경우가 많아, 이산수학과 전산학 이론 논문 전반에 걸쳐 기초 도구로 인용됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 복잡한 점화식으로만 표현되던 수열을, 생성함수라는 도구를 거쳐 계산 가능한 수식으로 바꾸어냈다는 뜻입니다. 조합론, 알고리즘 분석, 이산수학 논문에서 수열의 개수를 세거나 점화 관계를 푸는 기초 배경으로 자주 인용됩니다.
그래프이론에서는 특정 구조(독립집합, 매칭 등)의 개수를 직접 나열하기 어려울 때, 지수생성함수를 이용해 이들의 증가 패턴을 대수적으로 분석하는 방식이 사용됩니다.
정수론에서 정수를 여러 방식으로 쪼개는 경우의 수(분할)를 다룰 때도, 생성함수는 복잡한 조합적 문제를 다루기 쉬운 함수의 형태로 바꾸는 표준적인 방법입니다.
조금 더 깊게 보면
생성함수는 계수를 그대로 다루는 일반생성함수(ordinary generating function)와, 계수를 n!로 나눠 다루는 지수생성함수(exponential generating function)로 나뉘며, 다루는 조합적 대상의 성격(순서가 있는지 없는지 등)에 따라 어떤 것을 쓸지가 달라집니다. 또한 논문에서는 생성함수 자체의 급수가 실제로 수렴하는 범위(수렴반경)까지는 크게 신경 쓰지 않고, 형식적 거듭제곱급수(formal power series)로서 계수 관계만을 다루는 경우가 많다는 점도 함께 알아두면 이해에 도움이 됩니다.
주의할 점
생성함수는 이름이 비슷한 "적률생성함수(moment generating function)"와 혼동하기 쉽지만 서로 다른 개념입니다. 적률생성함수는 확률변수의 통계적 특성을 다루는 확률론의 도구인 반면, 여기서 다루는 생성함수는 점화식으로 정의된 수열을 대수적으로 다루기 위한 조합론의 도구입니다.