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 + ··· + 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 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 = an1 + an2 a0 = 1 a1 = 1
Fibonacci number Fn-1+Fn-2ifn≥2， En= if n =1 0 if n 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 个公公 Recursion: Ck Cn-1-k Co=1forn≥1， m-1 Cn=∑CCn-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: 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