南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）Generating Function

Fibonacci number = 1+√5 0=1-v6 2 2 -店(-)

Fibonacci number ￾ = 1 + ￾5 2 ￾ ˆ = 1 ￾ ⇥5 2 Fn = 1 ⇥5 ￾ ￾n ￾ ￾ ˆ n ⇥

2 3 11 8 5 1 1/0 91 1 1/03 (0

(Fn-1+Fn-2 i fn≥2， generating function: Fn 1 if n=1 G(2)=>Fn.am 0 if n =0. m>0 recursion: G()=F+Fx+∑Fn”=x+∑Fn-1x”+∑Fn-2xn m>2 m>2 m>2 ∑F-1xn=∑n-1x”=∑ Fnxn+1 =xG(c) m≥2 m>1 m≥0 ∑Fn-2n=∑Fnxn+2=x2G() n≥2 m>0 identity: G(c)=x+(+x2)G(x)

￾ n￾2 Fn￾1xn + ￾ n￾2 Fn￾2xn Fn = ￾ ⌅⇤ ⌅⇥ Fn￾1 + Fn￾2 if n ￾ 2, 1 if n = 1 0 if n = 0. generating function: G(x) = ￾ n￾0 Fnxn G(x) = F0 + F1x + ￾ n￾2 Fnxn = x+ = ￾ n￾0 Fnxn+1 = ￾ n￾0 Fnxn+2 ￾ n￾2 Fn￾2xn = x2G(x) = xG(x) G(x) = x + (x + x2)G(x) recursion: identity: ￾ n￾2 Fn￾1xn = ￾ n￾1 Fn￾1xn

(Fn-1+Fn-2 fn≥2， generating function: Fn 1 ifn =1 G()=>Fnan 0 if n =0. n>0 identity: G(x)=x+(x+x2)G(x) T solution: G()=1-x-x2 =Taylor denote 0= 1+5 6= 1-5 2 2 T 1 1 1 1 1-x-x2 V5'1-V51-0x

Fn = ￾ ⌅⇤ ⌅⇥ Fn￾1 + Fn￾2 if n ￾ 2, 1 if n = 1 0 if n = 0. generating function: G(x) = ￾ n￾0 Fnxn G(x) = x + (x + x2 identity: )G(x) G(x) = x 1 ￾ x ￾ x2 solution: Taylor ? ￾ = 1 + ￾5 2 ￾ ˆ = 1 ￾ ￾5 2 x 1 ￾ x ￾ x2 = 1 ￾5 · 1 1 ￾ ￾x ￾ 1 ￾5 · 1 1 ￾ ￾ ˆ x denote =?

(Fn-1+Fn-2 fn≥2， generating function: Fn 1 ifn =1 G(c)=Fnx” 0 if n=0. m>0 identity: G(x)=x+(x+x2)G(z) solution: G(x)= 1-x-x2 1 1 1 1 V51-r-V51-a 店r-店∑ m>( n>0 =后(-） n>

Fn = ￾ ⌅⇤ ⌅⇥ Fn￾1 + Fn￾2 if n ￾ 2, 1 if n = 1 0 if n = 0. generating function: G(x) = ￾ n￾0 Fnxn G(x) = x + (x + x2 identity: )G(x) G(x) = x 1 ￾ x ￾ x2 solution: = 1 ￾5 ￾ n￾0 (￾x) n ￾ 1 ￾5 ￾ n￾0 (￾ ˆ x) n = ￾ n￾0 1 ￾5 ￾ ￾n ￾ ￾ ˆ n ￾ xn = 1 ￾5 · 1 1 ￾ ￾x ￾ 1 ￾5 · 1 1 ￾ ￾ ˆ x