(1l+x2)=1+2 (1t-x2)?=14+2r4+2” (1+x)?=14+32432° +2” (1+2)’=14+424+ 62°4+-42’+2’

(1+x)°=1+5r+102°+102°+52’+2°

atay”=(2)+(e ie po ete

위의 항등식에서 (1+#)”은 바로 //개의 원소에서 《개를 뽑는 수에 대한 생성함수가 됩니다. 일반적인 생성함수의 형태 살펴보면 다음과 같습니다.

얀 is \

Kd

** 생성함수의 정의 을 /개의 자료로 나타낼 수 있는 모든 경우의 수라고 하자. 만약 re )가 a, 대하여 다음과 같은 다항식을 갖는다고 하자. 062) rat rage + tae +

이때, g(a) S 생성함수라 한다.