组合数学-母函数

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 组合数学母函数 任 世 军 Email: renshijun 哈尔滨工业大学 计算机学院 December 16, 2014 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20141 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 目录 . . . 1 普通母函数 . . . 2 指数母函数 . . . 3 母函数的基本运算 . . . 4 母函数的应用 . . . 5 在组合恒等式中的应用 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20142 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 普通母函数 . Defi nition . . . . . . . . 给定一无穷序列a0,a1, ,an,(简记为an n=0)， 称形式幂级 数 i=0aix i 为序列an n=0 的普通母函数（发生、 生成函数）。 f(x) 是形式无穷级数， 不管其收敛性； x 为形式变元， f(x) 为形式幂级数； 序列与母函数一一对应； 母函数是序列的另一表达形式； 有限序列也可用母函数表示； 可与二项式定理结合应用。 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20143 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 普通母函数 . Defi nition . . . . . . . . 给定一无穷序列a0,a1, ,an,(简记为an n=0)， 称形式幂级 数 i=0aix i 为序列an n=0 的普通母函数（发生、 生成函数）。 f(x) 是形式无穷级数， 不管其收敛性； x 为形式变元， f(x) 为形式幂级数； 序列与母函数一一对应； 母函数是序列的另一表达形式； 有限序列也可用母函数表示； 可与二项式定理结合应用。 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20143 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 普通母函数 . Example . . . . . . . . 求序列C0 n,C1n, ,Cnn 的普通母函数。 解:由定义知， 序列的普通母函数为C0 n+ C1nx + + Cnnxn= (1 + x)n。 . Example . . . . . . . . 求序列C0 n1,C1n,C2n+1, ,(1)kCkn+k1, 的普通母函数。 解:由定义知， 序列的普通母函数为 C0 n1C 1 nx + C 2 n+1x 2 + (1)kCk n+k1x k + = k=0 (1)kCk n+k1x k = k=0 (1)kCn kx k = (1 + x)n 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20144 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 普通母函数 . Example . . . . . . . . 求序列C0 n,C1n, ,Cnn 的普通母函数。 解:由定义知， 序列的普通母函数为C0 n+ C1nx + + Cnnxn= (1 + x)n。 . Example . . . . . . . . 求序列C0 n1,C1n,C2n+1, ,(1)kCkn+k1, 的普通母函数。 解:由定义知， 序列的普通母函数为 C0 n1C 1 nx + C 2 n+1x 2 + (1)kCk n+k1x k + = k=0 (1)kCk n+k1x k = k=0 (1)kCn kx k = (1 + x)n 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20144 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 普通母函数 . Example . . . . . . . . 求序列C0 n,C1n, ,Cnn 的普通母函数。 解:由定义知， 序列的普通母函数为C0 n+ C1nx + + Cnnxn= (1 + x)n。 . Example . . . . . . . . 求序列C0 n1,C1n,C2n+1, ,(1)kCkn+k1, 的普通母函数。 解:由定义知， 序列的普通母函数为 C0 n1C 1 nx + C 2 n+1x 2 + (1)kCk n+k1x k + = k=0 (1)kCk n+k1x k = k=0 (1)kCn kx k = (1 + x)n 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20144 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 普通母函数 . Example . . . . . . . . 求序列C0 n,C1n, ,Cnn 的普通母函数。 解:由定义知， 序列的普通母函数为C0 n+ C1nx + + Cnnxn= (1 + x)n。 . Example . . . . . . . . 求序列C0 n1,C1n,C2n+1, ,(1)kCkn+k1, 的普通母函数。 解:由定义知， 序列的普通母函数为 C0 n1C 1 nx + C 2 n+1x 2 + (1)kCk n+k1x k + = k=0 (1)kCk n+k1x k = k=0 (1)kCn kx k = (1 + x)n 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20144 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 普通母函数 . Example . . . . . . . . 证明(1 4x) 1 2是序列C0 0,C12,C24, ,Cn2n, 的普通母函数。 证:由牛顿二项式定理有 (14x) 1 2= 1 + k=1 (1 2 k ) (4x)k= 1 + k=1 1 2( 1 2 1)(1 2 k + 1) k! (4x)k =1 + k=1 4k 1 3 5 (2k 1) 2kk! xk= 1 + k=1 2kk! 1 3 5 (2k 1) k!k! xk =1 + k=1 (2 4 2k) (1 3 5 (2k 1) k!k! xk= 1 + k=1 (2k)! k!k! xk =1 + k=1 (2k k ) xk= (0 0 ) + (2 1 ) x + (4 2 ) x2+ + (2k k ) xk+ 由定义知， (1 4x)1/2是序列C0 0,C12,C24, ,Cn2n, 的普通母函数。 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20145 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 普通母函数 . Example . . . . . . . . 证明(1 4x) 1 2是序列C0 0,C12,C24, ,Cn2n, 的普通母函数。 证:由牛顿二项式定理有 (14x) 1 2= 1 + k=1 (1 2 k ) (4x)k= 1 + k=1 1 2( 1 2 1)(1 2 k + 1) k! (4x)k =1 + k=1 4k 1 3 5 (2k 1) 2kk! xk= 1 + k=1 2kk! 1 3 5 (2k 1) k!k! xk =1 + k=1 (2 4 2k) (1 3 5 (2k 1) k!k! xk= 1 + k=1 (2k)! k!k! xk =1 + k=1 (2k k ) xk= (0 0 ) + (2 1 ) x + (4 2 ) x2+ + (2k k ) xk+ 由定义知， (1 4x)1/2是序列C0 0,C12,C24, ,Cn2n, 的普通母函数。 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20145 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 普通母函数 . Example . . . . . . . . 求序列0,1 2 3,2 3 4, ,n(n + 1)(n + 2), 的普通母函数 解:由二项式定理的推论知 1 1x = 1+x+x2+x3+xk+， 逐次微分得 1 1 x = n=0 xn 1 (1 x)2 = n=1 nxn1 2 (1 x)3 = n=2 n(n 1)xn2 6 (1 x)4 = n=3 n(n 1)(n 2)xn3 同乘x 有 6x (1 x)4 = n=3 n(n 1)(n 2)xn2= n=1 (n + 2)(n + 1)(n)xn 因此函数 6x (1x)4 是序列0,1 2 3,2 3 4, ,n(n + 1)(n + 2), 的普通母 函数。 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20146 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 普通母函数 . Example . . . . . . . . 求序列0,1 2 3,2 3 4, ,n(n + 1)(n + 2), 的普通母函数 解:由二项式定理的推论知 1 1x = 1+x+x2+x3+xk+， 逐次微分得 1 1 x = n=0 xn 1 (1 x)2 = n=1 nxn1 2 (1 x)3 = n=2 n(n 1)xn2 6 (1 x)4 = n=3 n(n 1)(n 2)xn3 同乘x 有 6x (1 x)4 = n=3 n(n 1)(n 2)xn2= n=1 (n + 2)(n + 1)(n)xn 因此函数 6x (1x)4 是序列0,1 2 3,2 3 4, ,n(n + 1)(n + 2), 的普通母 函数。 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20146 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 指数母函数 . Defi nition . . . . . . . . 给定一无穷序列a0,a1, ,an,(简记为an n=0)， 称函 数fe(x) = i=0ai xi i! 为序列an n=0 的指数母函数。 注： fe(x) 也是形式幂函数。经常可结合以下公式运算： eax= 1 + a x 1! + a2 x2 2! + a3 x3 3! + + ak xk k! + ex= 1 x 1! + x2 2! x3 3! + + (1)k xk k! + sin(x) = x 1! + x3 3! + x5 5! + + xk k! + = ex ex 2 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20147 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 指数母函数 . Defi nition . . . . . . . . 给定一无穷序列a0,a1, ,an,(简记为an n=0)， 称函 数fe(x) = i=0ai xi i! 为序列an n=0 的指数母函数。 注： fe(x) 也是形式幂函数。经常可结合以下公式运算： eax= 1 + a x 1! + a2 x2 2! + a3 x3 3! + + ak xk k! + ex= 1 x 1! + x2 2! x3 3! + + (1)k xk k! + sin(x) = x 1! + x3 3! + x5 5! + + xk k! + = ex ex 2 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20147 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 指数母函数 . Example . . . . . . . . 设n 是整数， 求序列P(n,0),P(n,1), ,P(n,n) 的指数母函数fe(x)。 解:公式P(n,r) = r!C(n,r)， 有fe(x) = P(n,0) + P(n,1) x 1! + P(n,2)x 2 2! + + P(n,k)x k k! + + P(n,n)x n n! = C(n,0)+C(n,1)x+C(n,2)x2+C(n,k)xk+C(n,n)xn= (1+x)n 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20148 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 指数母函数 . Example . . . . . . . . 设n 是整数， 求序列P(n,0),P(n,1), ,P(n,n) 的指数母函数fe(x)。 解:公式P(n,r) = r!C(n,r)， 有fe(x) = P(n,0) + P(n,1) x 1! + P(n,2)x 2 2! + + P(n,k)x k k! + + P(n,n)x n n! = C(n,0)+C(n,1)x+C(n,2)x2+C(n,k)xk+C(n,n)xn= (1+x)n 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20148 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 指数母函数 . Example . . . . . . . . 求序列P(0,0),P(2,1),P(4,2), ,P(2n,n), 的指数母函数fe(x)。 解:由公式P(n,r) = r!C(n,r)， 以及上例的结论， 有 fe(x) =P(0,0) + P(2,1) x 1! + P(4,2)x 2 2! + + P(2n,n)x n n! + = (0 0 ) + (2 1 ) x + (4 2 ) x2+ + (2n n ) xn+ =(1 4x) 1 2 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20149 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 指数母函数 . Example . . . . . . . . 求序列P(0,0),P(2,1),P(4,2), ,P(2n,n), 的指数母函数fe(x)。 解:由公式P(n,r) = r!C(n,r)， 以及上例的结论， 有 fe(x) =P(0,0) + P(2,1) x 1! + P(4,2)x 2 2! + + P(2n,n)x n n! + = (0 0 ) + (2 1 ) x + (4 2 ) x2+ + (2n n ) xn+ =(1 4x) 1 2 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 20149 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 指数母函数 . Example . . . . . . . . 求序列1,2, ,n, 的指数母函数fe(x)。其中 是实数。 解:由定义， 有fe(x) = 1 + x 1! + 2 x 2 2! + + n x n n! + = ex 特别地： 若 = 1， 则序列1,1, ,1, 的指数母函数为ex。 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201410 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 指数母函数 . Example . . . . . . . . 求序列1,2, ,n, 的指数母函数fe(x)。其中 是实数。 解:由定义， 有fe(x) = 1 + x 1! + 2 x 2 2! + + n x n n! + = ex 特别地： 若 = 1， 则序列1,1, ,1, 的指数母函数为ex。 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201410 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 指数母函数 . Example . . . . . . . . 求序列1,1 4,1 4 7, ,1 4 7 (3n + 1), 的指数母函数。 解:由定义和二项式定理， 有 fe(x) =1 + (1 4) x 1! + (1 4 7)x 2 2! + + 1 4 7 (3n + 1)x n n! + = n=0 4 7 (3n + 1) n! xn= n=0 4 3 7 3 (3n+1) 3 n! 3nxn = n=0 (4 3 ) (4 3 1) (4 3 n + 1) n! (3x)n = n=0 (4 3 n ) (3x)n= (1 3x) 4 3 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201411 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 指数母函数 . Example . . . . . . . . 求序列1,1 4,1 4 7, ,1 4 7 (3n + 1), 的指数母函数。 解:由定义和二项式定理， 有 fe(x) =1 + (1 4) x 1! + (1 4 7)x 2 2! + + 1 4 7 (3n + 1)x n n! + = n=0 4 7 (3n + 1) n! xn= n=0 4 3 7 3 (3n+1) 3 n! 3nxn = n=0 (4 3 ) (4 3 1) (4 3 n + 1) n! (3x)n = n=0 (4 3 n ) (3x)n= (1 3x) 4 3 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201411 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 普通母函数与指数母函数间的关系 . Theorem . . . . . . . . 设f(x)和fe(x)?为序列an n=0 的普通和指数母函数， 则f(x) = + 0 esfe(sx)ds. 证:由指数母函数的定义知 fe(sx) = n=0 an (sx)n n! 上式两端同乘es并从0 到 积分得 + 0 esfe(sx)ds = + 0 n=0 anes snxn n! ds = n=0 an xn n! + 0 snesds 而 + 0 snesds = n!， 所以 + 0 esfe(sx)ds = n=0 anxn= f(x) 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201412 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 普通母函数与指数母函数间的关系 . Theorem . . . . . . . . 设f(x)和fe(x)?为序列an n=0 的普通和指数母函数， 则f(x) = + 0 esfe(sx)ds. 证:由指数母函数的定义知 fe(sx) = n=0 an (sx)n n! 上式两端同乘es并从0 到 积分得 + 0 esfe(sx)ds = + 0 n=0 anes snxn n! ds = n=0 an xn n! + 0 snesds 而 + 0 snesds = n!， 所以 + 0 esfe(sx)ds = n=0 anxn= f(x) 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201412 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 母函数基本运算 . Theorem . . . . . . . . 设A(x),B(x),C(x)?是序列an n=0， bn n=0 和cn n=0 的普通母函数， 则 (1). C(x) = A(x) + B(x)?且?ci= ai+ bi,(i = 0,1,2, ,n,). (2).C(x) = A(x)B(x)?且?ci= i k=0akbik, (i = 0,1,2, ,n,). 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201413 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 母函数基本运算 . Example . . . . . . . . 设A(x) 是序列an n=0 的普通母函数， 则A(x) 1x 是序 列a0,a0+ a1, ,a0+ a1+ + an, 的普通母函数。 证:上面定理中的序列bn= 1,n = 0,1,2,， 其母函数为 1 1x = 1 + x + x2+ x3+ + xn+ 所以A(x) 1x 作为母函数其序列 为ci= i k=0akbik = i k=0ak = a0+ a1+ + ai,i = 0,1,2,. 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201414 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 母函数基本运算 . Example . . . . . . . . 设A(x) 是序列an n=0 的普通母函数， 则A(x) 1x 是序 列a0,a0+ a1, ,a0+ a1+ + an, 的普通母函数。 证:上面定理中的序列bn= 1,n = 0,1,2,， 其母函数为 1 1x = 1 + x + x2+ x3+ + xn+ 所以A(x) 1x 作为母函数其序列 为ci= i k=0akbik = i k=0ak = a0+ a1+ + ai,i = 0,1,2,. 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201414 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 母函数基本运算 . Example . . . . . . . . 求和 n i=0 i2的值。 解: 1 1 x = i=0 xi， 两边微分， 再乘以x 有 x (1 x)2 = i=1 ixi， 再做同样的操作 得 x + x2 (1 x)3 = i=1 i2xi， 所以 x + x2 (1 x)3 为序列0,1,22,32, ,n2, 的母函数， 与 序列1,1, ,1 的母函数 1 1x 相成为 n i=0 i2的母函数。而 x + x2 (1 x)4 = x (1 x)4 + x2 (1 x)4 = i=0 Cii+3xi+1+ i=0 Cii+3xi+2= x + i=2 C3 i+2+ C 3 i+1 xi， 于是 n i=0 i2= C3 n+2+ C3n+1= (n+2)(n+1)n 6 + (n+1)n(n1) 6 = (n+1)n(2n+1) 6 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201415 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 母函数基本运算 . Example . . . . . . . . 求和 n i=0 i2的值。 解: 1 1 x = i=0 xi， 两边微分， 再乘以x 有 x (1 x)2 = i=1 ixi， 再做同样的操作 得 x + x2 (1 x)3 = i=1 i2xi， 所以 x + x2 (1 x)3 为序列0,1,22,32, ,n2, 的母函数， 与 序列1,1, ,1 的母函数 1 1x 相成为 n i=0 i2的母函数。而 x + x2 (1 x)4 = x (1 x)4 + x2 (1 x)4 = i=0 Cii+3xi+1+ i=0 Cii+3xi+2= x + i=2 C3 i+2+ C 3 i+1 xi， 于是 n i=0 i2= C3 n+2+ C3n+1= (n+2)(n+1)n 6 + (n+1)n(n1) 6 = (n+1)n(2n+1) 6 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201415 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 母函数基本运算 . Theorem . . . . . . . . ?bk= 0?k l? akl?则k l 则B(x) = xlA(x) 证:由b0= b1= = bl1= 0， 且bl= a0,bl+1= a1, ,bk= akl,， 知B(x) = b0 x0+ b1x1+ + bl1xl1+ blxl+ bl+1xl+1+ = blxl+ bl+1xl+1+ = xl(a0+ a1x + a2x2+ ) = xlA(x) 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201416 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 母函数基本运算 . Theorem . . . . . . . . ?bk= 0?k l? akl?则k l 则B(x) = xlA(x) 证:由b0= b1= = bl1= 0， 且bl= a0,bl+1= a1, ,bk= akl,， 知B(x) = b0 x0+ b1x1+ + bl1xl1+ blxl+ bl+1xl+1+ = blxl+ bl+1xl+1+ = xl(a0+ a1x + a2x2+ ) = xlA(x) 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201416 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 母函数基本运算 . Theorem . . . . . . . . ?bk= ak+l(k 0)， 则B(x) = A(x) l1 k=0 akxk xl 。 证:B(x) = b0 x0+ b1x1+ + bkxk+ = alx0+ al+1x1+ al+2x2+ = alxl+ al+1xl+1+ al+2xl+2+ xl = A(x) l1 k=0 akxk xl . Theorem . . . . . . . . ?bk= k i=0 ai(k 0)， 则B(x) = A(x) 1 x. 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201417 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 母函数基本运算 . Theorem . . . . . . . . ?bk= ak+l(k 0)， 则B(x) = A(x) l1 k=0 akxk xl 。 证:B(x) = b0 x0+ b1x1+ + bkxk+ = alx0+ al+1x1+ al+2x2+ = alxl+ al+1xl+1+ al+2xl+2+ xl = A(x) l1 k=0 akxk xl . Theorem . . . . . . . . ?bk= k i=0 ai(k 0)， 则B(x) = A(x) 1 x. 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201417 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 母函数基本运算 . Theorem . . . . . . . . ? k=0 ak?，bk= j=k aj， 则B(x) = A(1) xA(x) 1 x 证: 1b0=a0+a1+a2+=A(1) xb1=a1+a2+=A(1) a0 x2b2=a2+=A(1) a0 a1 B(x) = A(1)(1+x+x2+)a0 x(1+x+x2+)a1x2(1+x+x2+) = (A(1) x(a0+ a1x + a2x2+ )(1 + x + x2+ ) = A(1) xA(x) 1 x 任世军 (哈尔滨工业大学)组合数学 母函数December 16, 201418 / 41 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 母