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

Compositions by 1 and 2 of compositions of n #of(x1,x2,.,xk） with summands from for some k≤m {1,2} C1十··+Ck= xi∈{1,2} an an-1 +an-2 a0=1a1=1 Case.I Ck=1 x1+···+ck-1=m-1 Case.2 xk=2 x1+···+xk-1=m-2

# of compositions of n with summands from {1,2} xi ￾ {1, 2} Case.1 Case.2 xk = 1 xk = 2 x1 + ··· + xk￾1 = n ￾ 1 x1 + ··· + xk￾1 = n ￾ 2 Compositions by 1 and 2 for some k ￾ n # of (x1, x2,...,xk) x1 + ··· + xk = n an = an￾1 + an￾2 a0 = 1 a1 = 1

Dominos 2 domino:1 #of tilings 2 …□ n an an-1+an-2 a0=1a1=1 Case.I 2×(n-1) Case.2 ☐…2x(n-2)

Dominos domino: 1 2 ￾ 2 n # of tilings Case.1 Case.2 2×(n-1) 2×(n-2) an = an￾1 + an￾2 a0 = 1 a1 = 1

Fibonacci number Fn-1+Fn-2ifn≥2， if n =1 fm=0

Fibonacci number Fn = ￾ ⌅⇤ ⌅⇥ Fn￾1 + Fn￾2 if n ￾ 2, 1 if n = 1 0 if n = 0

full parenthesization of n+1 factors ((ab)c)d (a(bc))d (ab)(cd)a((bc)d)a(b(cd)) full binary trees with n+1 leaves 心公人公

full binary trees with n+1 leaves ((ab)c)d (a(bc))d (ab)(cd) a((bc)d) a(b(cd)) full parenthesization of n+1 factors

Catalan number On:of full binary trees with n+1 leaves 公a公 Recursion: Ck Cn-1-k Co=1forn≥1， m-1 Cn =>Ck.Cn-1-k k=0

Cn = n ￾￾1 k=0 CkCn￾1￾k C0 = 1 for n ￾ 1, Ck Cn￾1￾k Cn : # of full binary trees with n+1 leaves Catalan Number Recursion:

Generating Functions

Generating Functions

Generating Functions: Cartbndge Sdis n Advanced Mathelatcs 49 Enumerative Combinatorics Volume I "the most useful but most RICHARD P.STANLEY difficult to understand method (for counting) CONCRETE MATHEMATICS A FOUNDATION FOR COMPUTER SCIENCE GRAHAM KNUTH PATASHNIK "the most powerful way to deal with sequences of numbers,as far as anybody knows

“the most useful but most difficult to understand method (for counting)” Generating Functions: “the most powerful way to deal with sequences of numbers, as far as anybody knows

generate enumerate all subsets of O,O,O} (x0+x2)(x0+x2)(x0+x2） zOxOz0 +x0z0z1+x0z1z0+x0x1z1 +x1x0x0+x1a0x1+x1x1x0+x1x1x1 (1+x)3=1+3x+3x2+x3 coefficient ofx:of k-subsets

{ , , } enumerate all subsets of generate (x0 + x1)(x0 + x1)(x0 + x1) = + + + + + + + x1 x0x0x0 x0x0x1 x0 x0 x1 x0 x1 x1 x0 x0 x1 x0 x1 x1 x0 x1 x1 x1 x1 (1 + x) 3 =1+3x + 3x2 + x3 coefficient of xk : # of k-subsets

{○，○，○， ●，●，●，●， ○，○，○，○，○} (1+x+x2+x3) (1+x+x2+x3+x4) (1+x+x2+x3+x4+x5) 三 1+3+6x2+10x3+14x4+17x5+18x6 +17x7+14x8+10x9+6x10+3x11+x12

(1 + x + x2 + x3) (1 + x + x2 + x3 + x4) (1 + x + x2 + x3 + x4 + x5) { } , , , , , , , , , , , = 1+3x + 6x2 + 10x3 + 14x4 + 17x5 + 18x6 +17x7 + 14x8 + 10x9 + 6x10 + 3x11 + x12

Double Decks choose m cards from 2 decks of n cards (+1+x)(唱+2+x)…(a%+x%+x品) of m-order terms coefficient of xm in (1+x+x2)

Double Decks (x0 1 + x1 1 + x2 1) (x0 2 + x1 2 + x2 2) ···(x0 n + x1 n + x2 n) # of m-order terms (1 + x + x2) n coefficient of xm in 2 deck of s n cards choose m cards from