应用(生成函数求法) 例4红、白、兰涂色1Xn的方格,要求偶数个为白色, 问有多少方案? 解设方案数为an G2(x)=(+x,+…)(1+x+m+… (ee e e-+-e ∑3"n+,∑=∑ +1x n=0 ni 2 nk 3n+1
6 例 4 红、白、兰涂色 1×n 的方格，要求偶数个为白色， 问有多少方案？ 解 设方案数为 an 2 3 1 2 ! 3 1 2 ! 1 ! 3 2 1 2 1 2 1 ( ) 21 ...) 2! ...)(1 2! ( ) (1 0 0 0 2 3 2 2 2 + = + = + = = + = + = + + + + + ∑ ∑ ∑ ∞ = ∞ = ∞ = − n n n n n n n n n n x x x x x e a n x n x n x e e e e e x x x G x 应用（生成函数求法）
递推方程的求法 解法2递推方程 an=2an1+(3-an1) =2 an=amn-1t3 解得P=3/2,an=32 通解an=C+32 代入初值得C=1/2 解为an=(3+1)2
7 解法 2 递推方程 an = 2an-1 + (3n-1− an-1) a1 = 2 an = an-1 + 3n-1 a * n = P3n-1, 解得 P = 3/2, a*n = 3n/2 通解 an = C + 3n/2 代入初值得 C = 1/2 解为 an = (3n+1)/2 递推方程的求法
2.6高级计数 高级计数 Catalan数 第一类 Stirling数 第二类 Stirling数 讨论要点 定义 递推方程 恒等式 对应的组合问题 生成函数
8 22.6 高级计数 高级计数 Catalan数 第一类Stirling数 第二类Stirling数 讨论要点 定义 递推方程 恒等式 对应的组合问题 生成函数
Catalan数定义 定义一个凸n+1边形,通过不相交于n+1边形内 部的对角线把n+1边形拆分成的三角形个数,记 作hn,称为 Catalan数. 实例:h2h3=2, h:=5 △②公
9 Catalan数定义 定义 一个凸 n+1 边形，通过不相交于n+1边形内 部的对角线把 n +1边形拆分成的三角形个数，记 作hn，称为Catalan数. 实例：h2=1, h3=2, h4=5
递推方程 考虑n+1条边的多边形,端点A1,An1的边记为a, 以Ak+1(k=-1,2,,n-1)A1为边,An+14k+为另 边,构成三角形T,T将多边形划分成R1和R2两个 部分,分别为k+1边形和nk+1边形 k+1 hn=∑h m-k,n≥2 k=1 R R 2 2n-2 An n(n-1 A a+1
10 考虑 n+1 条边的多边形，端点 A1, An+1的边记为 a, 以 Ak+1（k=1, 2,…, n-1）A1为边，An+1Ak+1 为另一 边，构成三角形 T, T 将多边形划分成 R1和 R2两个 部分，分别为 k+1 边形和 n-k+1 边形. 1 , 2 1 1 1 = = ∑ ≥ − = − h h h h n n k n k n k ⎟⎟⎠⎞ ⎜⎜⎝⎛ −− = 1 1 2 2 nn n hn 递推方程