南京大学：《组合数学》课程教学资源（课堂讲义）生成函数 Generating functions

Compositions by 1 and 2 of compositions of n #of (1,2,...,xk) with summands from for some k≤m {1,2} x1十·+xk=n x∈{1,2} an an-1 an-2 a0=1a1=1 Case.I Xk=1 x1+··+ck-1=九-1 Case.2 k =2 1+..+xk-1=n-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 domino: 名 #of tilings 2 n an an-1 an-2 a0=1a1=1 Case.I 0… 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， En= if n =1 0 if n 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 个公公 Recursion: Ck Cn-1-k Co=1forn≥1， m-1 Cn=∑CCn-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: Enumerative Combinatorics "the most useful but most RICHARD P.STANLEY difficult to understand method (for counting)' CONCRETE MATHEMATICS AHAM KNUTH PATASHN "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} (x0+x2)(ax0+x2)(x0+x2) =2x020+x0xx1+20x'x0+20zlxI +x1x0x0+x1a0x1+x1x1a0+1xx1 (1+x)3=1+3a+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

O,O,O ●，●，0，●， ○，0,0,0，○} (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

(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 (9+1+x)(唱+吃+z)…(a%+xh+x品) of m-order terms coefficient of xm in (1+x+2)

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