생성함수 (수학)

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

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

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

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

정의[편집]

일반 생성함수[편집]

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

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

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

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

지수 생성함수[편집]

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

푸아송 생성 함수[편집]

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

람베르트 급수[편집]

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

벨 급수[편집]

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

    • Donald E. Knuth, The Art of Computer Programming, Volume 1 Fundamental Algorithms (Third Edition) Addison-Wesley. ISBN 0-201-89683-4. Section 1.2.9: "Generating Functions".
    • 틀:Apostol IANT pp.42–43