§22递推关系 令 x)=a1+a2x+a2x-+ +)-8x4(x)=-8a1x-8a2x2 (1-8x)A(x)=8+(a2-8a1)x+(a3-8a2)x2+…
§2.2 递推关系 令 + − = − − − = + + + 2 1 2 2 1 2 3 ) 8 ( ) 8 8 ( ) xA x a x a x A x a a x a x ____________________ (1−8x)A(x) = 8 + (a2 −8a1 )x + (a3 −8a2 )x 2 +
§22递推关系 (1-8x)4(x)=8+9x+9.10x2+ 9x8-71x 8+ 1-10x1-10x 8-71x 17 A(x) 9 (1-10x)(1-10x)21-8x1-10x ∑ (7·8+9:10)x 2 k=0 k-1 9 10-1
§2.2 递推关系 x x x x x A x x x 1 10 8 71 1 10 9 8 (1 8 ) ( ) 8 9 9 10 2 − − = − = + − = + + + = = + − + − = − − − = 0 (7 8 9 10 ) 2 1 ) 1 10 9 1 8 7 ( 2 1 (1 10 )(1 10 ) 8 71 ( ) k k k k x x x x x x A x 1 1 10 2 9 8 2 7 − − = + k k a
§22递推关系 例三:从n个元素4,a2…,a中取个进 行允许重复的组合。假定允许重复的组合 数用C(n,r)表示,其结果可能有以下两种 情况。 1)不出现某特定元素设为q其组合数 为C(nx相当于排除后从a1中取r个做,an 允许重复的组合
1）不出现某特定元素设为 ，其组合数 为 ，相当于排除 后从 中取r个做 允许重复的组合。 §2.2 递推关系 例三：从n个元素 中取r个进 行允许重复的组合。假定允许重复的组合 数用 表示，其结果可能有以下两种 情况。 a a an , , , 1 2 C(n,r) a1 C(n −1,r) a1 a an , , 2
§22递推关系 2)至少出现一个a1,取组合数为C(mn,r-1) 相当于从a1,a2…,an中取r1个做允许重复 的组合,然后再加上一个a1得从n个元素中 取r个允许重复的组合 依据加法原则可得 C(,r)=C(n,r-1)+C(n-1,r 因C(n,1)=n,C(n-1)=n-1,故令C(n,0)=1
§2.2 递推关系 2）至少出现一个 ，取组合数为 相当于从 中取r-1个做允许重复 的组合，然后再加上一个 得从n个元素中 取r个允许重复的组合。 a1 C(n,r −1) 1 a a a an , , , 1 2 依据加法原则可得： C(n,r) = C(n,r −1) +C(n −1,r) 因 C(n,1) = n,C(n −1,1) = n −1 ，故令 C(n,0) =1
§22递推关系 递推关系(2-2-3)带有两个参数n和r Gn(x)=C(n20)+C(n,1)x+C(n,2)x2+ xG (x)= C(n,0)x-C( nIx +)-Gn1(x)=-C(n-1,0)x-C(n-1,1)x (1-x)Gn(x)-Gn1(x)=0 (2-2-3)
§2.2 递推关系 递推关系(2-2-3)带有两个参数n和r。 + − = − − − − − − = − − − = + + + − G x C n x C n x xG x C n x C n x G x C n C n x C n x n n n ) ( ) ( 1,0) ( 1,1) ( ) ( ,0) ( ,1) ( ) ( ,0) ( ,1) ( ,2) 1 2 2 ____________________ (1 ) ( ) ( ) 0 (2 2 3) − x Gn x −Gn−1 x = − −