생성함수 (수학)
조합론의 개념
이 문서는 수학의 생성함수(모함수)에 관한 것입니다. 일반적인 역학에서의 모함수에 대해서는 모함수 (물리학) 문서를 참고하십시오.
와 같이 미지수의 계수가 수열의 각 항으로 되어 있는 멱급수 형태의 함수 즉, 그 수열을 계수로 하는 멱급수를 생성함수(生成函數, 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