생성함수(生成函數, generating function)는 주로 조합론과 수학적 분석에서 사용되는 개념으로, 시퀀스(sequence)나 수열의 정보를 다루는 데 활용된다. 생성함수는 일반적으로 시퀀스의 항들을 계수로 하는 수학적 함수로 표현된다.

가장 기본적인 형태의 생성함수는 무한급수 형태로 정의된다. 예를 들어, a₀, a₁, a₂, ...로 이루어진 수열 {aₙ}의 생성함수 G(x)는 다음과 같이 표현된다:

G(x) = a₀ + a₁x + a₂x² + a₃x³ + ... = Σ (n=0부터 ∞) aₙxⁿ

여기서 x는 보통 실수 또는 복소수이며, Σ는 시그마 기호로 무한급수를 나타낸다. 이와 같이 생성함수를 사용하면 복잡한 수열이나 조합적인 문제를 해결하는 데 많은 이점이 있다.

특정한 타입의 수열에 대해, 생성함수는 그 수열의 성질을 연구하는 데 큰 도움이 된다. 예를 들어, 합동식, 재귀적 관계, 조합적 성질 등이 생성함수를 통해 유도될 수 있다. 생성함수의 다양한 종류가 있으며, 대표적으로는 다음과 같은 것들이 있다:

1. 정적생성함수(ordinary generating function): 일반적인 형태로, 시퀀스의 항들을 직접 사용한 생성함수.

2. 제너레이트함수(exponential generating function): 다음과 같이 정의되며, n!로 나누어진 항을 계수로 사용하는 형태이다.

G(x) = Σ (n=0부터 ∞) aₙ * (xⁿ / n!)

3. 큐비함수(cubic generating function): 주로 그래프 이론이나 대칭군의 성질을 연구할 때 사용된다.

생성함수는 푸리에 급수, 테일러 급수 등과 같이 함수의 분석에도 적용되며, 다양한 수학적 문제를 해결하는 데 중요한 역할을 한다. 조합론에서는 특히 생성함수를 통해 조합적 수량을 계산하고, 경로계산 및 그래프의 성질 분석에 이용되기도 한다.

생성함수의 응용은 수학 외에도 통계학, 물리학, 컴퓨터 과학 등 다방면에 걸쳐 있으며, 문제를 모델링하고 분석하는 유용한 도구로 자리잡고 있다.