文章目录

参考博客 :

【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )【组合数学】生成函数 ( 线性性质 | 乘积性质 )【组合数学】生成函数 ( 移位性质 )【组合数学】生成函数 ( 求和性质 )【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )

一、使用生成函数求解不定方程解个数示例

111 克砝码 222 个 ,

222 克砝码 111 个 ,

444 克砝码 222 个 ,

可以称出哪些重量 , 有多少方案个数 ;

111 克的砝码 个数是 x1x_1x1​ 个 , 取值范围是 0≤x1≤20 \leq x_1 \leq 20≤x1​≤2 , 可取值 0,1,20 , 1, 20,1,2

222 克的砝码个数是 x2x_2x2​ 个 , 取值范围是 0≤x2≤10 \leq x_2 \leq 10≤x2​≤1 , 可取值 0,10,10,1

444 克的砝码个数是 x3x_3x3​ 个 , 取值范围是 0≤x3≤20 \leq x_3 \leq 20≤x3​≤2 , 可取值 0,1,20,1,20,1,2

x1+2x2+4x3=rx_1 + 2x_2 + 4x_3 = rx1​+2x2​+4x3​=r , 其中 rrr 代表可以称出的重量 ,

写出上述 , 带限制条件 , 并且带系数 的不定方程非负整数解的 生成函数 :

x1x_1x1​ 项 , 带限制条件 , 没有系数 , 其 底是 yyy , 幂取值 0,1,20 , 1, 20,1,2 , 对应的生成函数项是 (1+y+y2)( 1 + y + y^2 )(1+y+y2)

x2x_2x2​ 项 , 带限制条件 , 带系数 222 , 其 底是 y2y^2y2 , 幂取值 0,10,10,1 , 对应生成函数项是 (y2)0+(y2)1=1+y2(y^2)^0 + (y^2)^1 = 1+ y^2(y2)0+(y2)1=1+y2

x3x_3x3​ 项 , 带限制条件 , 带系数 444 , 其 底是 y4y^4y4 , 幂取值 0,1,20,1, 20,1,2 , 对应生成函数项是 (y4)0+(y4)1+(y4)2=1+y4+y8(y^4)^0 + (y^4)^1 + (y^4)^2 = 1+ y^4 + y^8(y4)0+(y4)1+(y4)2=1+y4+y8

将上述三项乘起来 , 并展开 :

G(x)=(1+y+y2)(1+y2)(1+y4+y8)G(x) = ( 1 + y + y^2 ) (1+ y^2) (1+ y^4 + y^8)G(x)=(1+y+y2)(1+y2)(1+y4+y8)

=1+y+2y2+y3+2y4+y5+2y6+y7+2y8+y9+2y10+y11+y12\ \ \ \ \ \ \ \ \ \ =1 + y + 2y^2 + y^3 + 2y^4 + y^5 + 2y^6 + y^7 + 2y^8 + y^9 + 2y^{10} + y^{11} + y^{12}=1+y+2y2+y3+2y4+y5+2y6+y7+2y8+y9+2y10+y11+y12

上述展开后的 yyy 的次幂数是重量 , 系数是 方案个数 , 如 2y82y^82y8 项表示 , 称出 888 克重量 , 有 222 个方案 ;

总体描述 :

111 项 : 表示 y0y^0y0 , 称出 000 克 , 有 000 种方案 ;yyy 项 : 表示 y1y^1y1 , 称出 111 克 , 有 111 种方案 ;2y22y^22y2 项 : 表示 2y22y^22y2 , 称出 222 克 , 有 222 种方案 ;y3y^3y3 项 : 表示 y3y^3y3 , 称出 333 克 , 有 111 种方案 ;2y42y^42y4 项 : 表示 2y42y^42y4 , 称出 444 克 , 有 222 种方案 ;y5y^5y5 项 : 表示 y5y^5y5 , 称出 555 克 , 有 111 种方案 ;2y62y^62y6 项 : 表示 2y62y^62y6 , 称出 666 克 , 有 222 种方案 ;y7y^7y7 项 : 表示 y7y^7y7 , 称出 777 克 , 有 111 种方案 ;2y82y^82y8 项 : 表示 2y82y^82y8 , 称出 888 克 , 有 222 种方案 ;y9y^9y9 项 : 表示 y9y^9y9 , 称出 999 克 , 有 111 种方案 ;2y102y^{10}2y10 项 : 表示 2y102y^{10}2y10 , 称出 101010 克 , 有 222 种方案 ;y11y^{11}y11 项 : 表示 y11y^{11}y11 , 称出 111111 克 , 有 111 种方案 ;y12y^{12}y12 项 : 表示 y12y^{12}y12 , 称出 121212 克 , 有 111 种方案 ;