南京大学：《组合数学 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

Changing Money (壹，伍)n=壹k伍n-k k=0 壹nx= 1 ∑伍nx” 1 n>0 1-C 1-2x5 n>0 》（壹，伍)mx”=》壹k伍n- m>0 m>0k=0 1 convolution! (1-x)(1-xc5)

= 1 (1 ￾ x)(1 ￾ x5) Changing Money ￾ n￾0 ၊nxn ￾ n￾0 ໿nxn = 1 1 ￾ x = 1 1 ￾ x5 (၊ ໿)n = ￾ n k=0 ၊k໿n￾k = ￾ n￾0 ￾ n k=0 ၊k໿n￾k convolution! ￾ n￾0 (၊ ໿)nxn

Changing Money 件 50 100 (壹，伍，拾，贰拾，伍拾，壹佰)nxn m≥0 1 (1-x)(1-x5)(1-x10)(1-x20)(1-2x50)(1-x100)

Changing Money ￾ n￾0 (၊ ໿ ൎ م ൎ໿ ൎ၊ϭ)nxn = 1 (1 ￾ x)(1 ￾ x5)(1 ￾ x10)(1 ￾ x20)(1 ￾ x50)(1 ￾ x100)

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

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 1. Recurrence: 2. Manipulation: 3. Solving: 4. Expanding:

Expanding generating functions Taylor's expansion: ce-∑0 m>0 Geometric sequence: C 1-b2 =∑ ab”xn m>0 01 G(x)=1-b1x +e+…+1 a2 ak [x"G(c)=a1b2 +a262 +...+akbr

Expanding generating functions G(x) = ￾ n￾0 G(n) (0) n! xn Taylor’s expansion: Geometric sequence: G(x) = a1 1 ￾ b1x + a2 1 ￾ b2x + ··· + ak 1 ￾ bkx [xn]G(x) = a1bn 1 +a2bn 2 + ··· + akbn k a 1 ￾ bx = ￾ n￾0 abnxn

Expanding generating functions Binomial theorem: Newton's formula I+er-S@ m>0 (1+))m=a(a-1)(a-2)…(a-n+1)(1+c)-n generalized binomial coefficient: =a(a-1a-2)…(a-n+1) n!

Expanding generating functions Binomial theorem: (1 + x) ￾ = ⇤ n￾0 ￾￾ n ⇥ xn ￾￾ n ⇥ = ￾(￾ ￾ 1)(￾ ￾ 2)···(￾ ￾ n + 1) n! generalized binomial coefficient: ((1 + x) ￾) (n) = ￾(￾ ￾ 1)(￾ ￾ 2)···(￾ ￾ n + 1)(1 + x) ￾￾n Newton’s formula