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: