생성함수 (수학)

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

수학에서 어떤 수열 an (n은 자연수)에 대하여,

f(x)= a_0+a_1x+a_2x^2+\cdots+a_nx^n+\cdots = \sum_{k=0}^\infty a_k x^k

와 같이 미지수의 계수가 수열의 각 항으로 되어 있는 멱급수 형태의 함수생성함수(generating function)라고 한다.

드 무아브르가 1730년에 일반 선형 점화식 문제를 풀기 위해 도입하였다.[1] 생성함수는 여러 경우에 이용되는데 예를 들어 어떤 수열에 대한 점화식을 이용해 일반항을 알아낼 때에도 쓰인다.



정의[편집]

일반 생성함수[편집]

수열 an일반 생성함수(ordinary generating function)는 다음과 같이 정의한다.

G(a_n;x)=\sum_{n=0}^\infty a_nx^n.

별도의 말이 없는 경우, 보통 생성함수는 일반생성함수를 말한다.

만약 an이산 확률 변수확률 질량 함수라면 그 생성함수는 확률 생성 함수라고 부른다.

일반생성함수는 인덱스가 여러 개인 배열로 일반화시킬 수 있다. 예를 들어, 2차원 배열 am,n (n, m은 자연수)의 일반생성함수는 다음과 같이 정의한다.

G(a_{m,n};x,y)=\sum_{m,n=0}^\infty a_{m,n}x^my^n.

지수 생성함수[편집]

수열 an지수 생성함수(exponential generating function)는 다음과 같이 정의한다.

\operatorname{EG}(a_n;x)=\sum _{n=0}^{\infty} a_n \frac{x^n}{n!}.

푸아송 생성 함수[편집]

수열 an푸아송 생성함수(poisson generating function)는 다음과 같이 정의한다.

\operatorname{PG}(a_n;x)=\sum _{n=0}^{\infty} a_n e^{-x} \frac{x^n}{n!} = e^{-x}\, \operatorname{EG}(a_n;x).

람베르트 급수[편집]

수열 an람베르트 급수(lambert series)는 다음과 같이 정의한다.

\operatorname{LG}(a_n;x)=\sum _{n=1}^{\infty} a_n \frac{x^n}{1-x^n}.

벨 급수[편집]

수열 an벨 급수(bell series)는 미지수 x와 소수 p 두 가지로 표현된 급수로,[2] 다음과 같이 정의한다.

\operatorname{BG}_p(a_n;x)=\sum_{n=0}^\infty a_{p^n}x^n.