利用数列的生成函数求一次不定方程非负整数解的个数

利用数列的生成函数求一次不定方程非负整数解的个数 利用数列的生成函数求一次不定方程非负整数解的个 数 2 0 0 5年第6期( 总第8 O期) 广西教育学院学报N O(6 (2 0 0 5(G U A N G X l J I A O Y U X U E Y U A N X U E B A O ( S e r i a l NO(8 O ) 利用数列的生成函数求一次不定方程非负整数解的个数唐兴国( 云南省红河州民族师范学校云南建水邮编:6 5 4 3 0 0 ) 摘要:给出求一次不定方程非负整数解的个数的定理和证明，并举例说明其应用。关键词:一次不定方程非负整数解个数中图分类号:O l 1 9 文献标识码:A 文章编号:1 0 0 6 ―9 4 1 0 ( 2 0 0 5 ) 0 6―0 0 7 7 ―0 2 1 (数列的生成函数的定义及有关运算定义幂级数( t ) = 荟t (c 叫做数列{ } 的生成函数。幂级数乘、除运算的规定设( t ) =?a ，( t ) =?是两个幂级数，K U 一v 则( 1 ) ( t ) ( t ) =( ?t ) f= c ，其中e k K U U U = ?a r 一;r =0 ( 2 ) 设- q ( t ) = d - c r是形式幂级数，且( t ) = K U ( t ) 1 ( t ) ，则称1 ( t ) 为甲( t ) 和( t ) 的商，记作1 ( t ) = 浩，其中1 ( t ) 的系数d 由下述方程确定:a o =b o c l o ，a 1=b l c l 0+b o d l ，a 2 =b 2 d 0+b 1 d l + h o d = ，…，a k =b k d 0 +b k 一1 d 1 +…+b o d k ，…。2 (两个常用的数列生成函数应用函数幂级数展开的，容易得到= 1 +t +【2 +l 3 +((’+ ‘( 1 ) =c :+c :+ t +c :+ t 2 +…+c :+ m t + …( 2 ) 3 (一次不定方程非负整数解的个数定理:设m?N，?N ( k=1 ，2 ，…，n ) ，则一次不定方程,t I x 1 +a 2 x 2 +…+ 】【n m ( 3 ) 的非负整数解的个数k 构成的数列{ } 的生成函数是( 4 ) 证明:在( 1 ) 式中分别用( k=1 ，2 ，…，n ) 代t 后再相乘可 得((((((((((((((((((((((((((((((((((! ((((((―((――――――(((一( 1 一t h) ( 1 一t ) …( 1 一t ) = ( 1 +t h+t 2 +…) ( 1 +t +t l 2+…) …( 1 +