[함수] 생성함수(generating function) 1부. 수열의 생성
Math/Logic/Set/Func.2011. 1. 6. 14:26 |
차례.
1. 정의
2. 상수수열
3. 생성함수의 합(sum) 과 곱(product)
4. 수열 1, 2, 3, 4, 5, ...
5. 이항계수 수열
6. 중복조합 수열
7. 피보나치 수열
1. 정의.
어떠한 수열의 생성함수는 그 수열을 계수로 하는 멱급수이다.
이것은 포말한 데피니션으로 급수의 수렴여부는 관심밖이라고 할 수 있다. 마치 수렴하는 것처럼 생각하기로 한다.
(수열) 생성함수라는 용어의 의미는 이 함수 G(x) 를 멱급수전개시 그 계수가 수열을 주기 때문에 붙여진 이름이다.
따라서, 함수에서 계수로 가는 맵 (즉, 펑셔널) 에 의해 본래의 수열로 돌아올 수 있다.
2. 첫번째 예제. 상수수열
상수수열의 생성함수는, 수열 1 , 1, 1, 1, 1, ... 의 생성함수를 구하는 것으로 충분하다. 어차피 상수배 하면 되니까...
따라서, 상수수열 a, a, a, a, a, ... 의 생성함수는 a / ( 1-x ) 이다.
이제 다시 G(x) = 1 / (1-x) 에서 원래의 수열 1, 1, 1, ... 로 돌아가는 것은 다음과 같이 하면 된다.
3. 생성함수의 합(sum) 과 곱(product)
수열 {an} 과 {bn} 의 생성함수 G1 과 G2 가 있을때, 두 생성함수의 합 G1+G2 는 ( 항별 덧셈을 가정하면 ) 새로운 수열 {cn } 의 생성함수인데, 여기서 cn = an + bn 이다.
두 생성함수의 곱 G1G2 는, 새로운 수열 {cn} 의 생성함수가 되는데, 이때 cn 은 다음과 같다.
이를 이용하면, 앞에서 구했던, 수열 1,1,1,1,1,... 의 생성함수 1 / ( 1-x ) 의 제곱이, 수열 1,2,3, ... 의 생성함수가 됨을 간단히 알 수 있다.
따라서, 자연수 수열 1,2,3, ... 의 생성함수는 1 / (1-x)^2 이다.
5. 이항계수 수열
실수범위까지 확장된 이항계수는 다음과 같다.
( 윗쪽 숫자는 실수이고, 아랫쪽 숫자는 음아닌 정수이다. )
위의 이항계수를 수열 an 으로 하는 생성함수는, 이항정리에 의해 바로 제공된다. ( 참조 : 테일러 급수, 이항계수 )
6. 중복조합 수열
중복조합의 수란, n 개의 종류에서 중복을 허용해서 k 개를 뽑는 경우의 수를 말한다. ( 각, 항목의 준비된 개수는 항상 충분하다 )
이것은 ( 1 + x + x^2 + ... ) ^ n 의 전개식에서 x^k 의 계수를 구하는 것과 같다.
그런데, 1 + x + x^2 + ... 이 1 / 1-x 이므로...
이 결과는 앞의 이항정리로 얻을수도 있다.
7. 피보나치 수열
피보나치 수열 : an = an-1 + an-2 ( n >= 2 ) , a0 = 0 , a1 = 1
