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 + ··· + xk1 = n 1 x1 + ··· + xk1 = n 2 Compositions by 1 and 2 for some k n # of (x1, x2,...,xk) x1 + ··· + xk = n an = an1 + an2 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 = an1 + an2 a0 = 1 a1 = 1
Fibonacci number Fn-1+Fn-2ifn≥2， if n =1 fm=0
Fibonacci number Fn = ⌅⇤ ⌅⇥ Fn1 + Fn2 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 CkCn1k C0 = 1 for n 1, Ck Cn1k 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