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

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

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￾2 Fn￾1xn + ￾ n￾2 Fn￾2xn = ￾ 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-2ifn≥2， generating function: 1 if n =1 G()=>Fnz" 0 if n=0. m>0 identity: G(x)=x+(x+z2)G(z) C solution: G(x)= 1-x-x2 1 1 1 1 expand: G()=V店'1-or V5 1-Ox 1+√5 2 -店 = n> n>0 v5 2 5(e-） 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: expand: G(x) = 1 ￾5 · 1 1 ￾ ￾x ￾ 1 ￾5 · 1 1 ￾ ￾ ˆ x = 1 ￾5 ￾ n￾0 (￾x) n ￾ 1 ￾5 ￾ n￾0 (￾ ˆ x) n = ￾ n￾0 1 ￾5 ￾ ￾n ￾ ￾ ˆ n ￾ xn ￾ = 1 + ￾5 2 ￾ ˆ = 1 ￾ ￾5 2

Solving Recurrence I.Recurrence: a0=0 a1 =1 an=an-1+an-2 2.Manipulation: G(c）=∑anx”=∑am-1x”+∑ an-2xn n>0 m>1 m>2 =x+(x+x2)G(x) 3.Solving: G()=1-x-2 4.Expanding: )=∑Goe n! m>0

1. Recurrence: 2. Manipulation: 3. Solving: 4. Expanding: Solving Recurrence a0 = 0 a1 = 1 an = an￾1 + an￾2 G(x) = ￾ n⇥0 anxn = ￾ n⇥1 an￾1xn + ￾ n⇥2 an￾2xn = x + (x + x2)G(x) G(x) = x 1 ￾ x ￾ x2 G(x) = ￾ n￾0 G(n) (0) n! xn

Operations on generating functions G(a)=∑gnin F(c)=∑fnxm n≥0 n≥0 right shift: xkG(c)=∑ 9n-kzn n≥k left shift: c-d9r-∑ xck n+kZn n≥0 addition: F(z)+G(a)=>(fn+gn)z" m>0 scaling: G(c)=∑c"gnx” n>0 convolution: F(c)G()=∑∑fkgn-kx” n≥0k=0 differentiation: G'(c)=(n+1)9n+1a” m>0

G(x) = ￾ n￾0 gnxn F(x) = ￾ n￾0 fnxn Operations on generating functions xkG(x) = ￾ n￾k gn￾kxn G(x) ￾ ￾k￾1 i=0 gixi xk = ￾ n￾0 gn+kxn F(x) + G(x) = ￾ n￾0 (fn + gn)xn G(cx) = ￾ n￾0 cngnxn F(x)G(x) = ￾ n￾0 ￾ n k=0 fkgn￾kxn G￾ (x) = ￾ n￾0 (n + 1)gn+1xn right shift: left shift: addition: scaling: convolution: differentiation:

Changing Money (壹，伍)n=壹伍n-k k=0 of ways to change n yuan using 壹圆 》壹nx”=1十x+x2+…= 1 m>0 1-c :of ways to change n yuan using 伍圆 》伍n”=1+x5+x10+…= 1 m>0 1-x

Changing Money ໿n ၊n : # of ways to change n yuan using 壹圆 : # of ways to change n yuan using 伍圆 ￾ n￾0 ၊nxn ￾ n￾0 ໿nxn =1+ x + x2 + ··· =1+ x5 + x10 + ··· = 1 1 ￾ x = 1 1 ￾ x5 (၊ ໿)n = ￾ n k=0 ၊k໿n￾k