文章目录
一、使用生成函数求解不定方程解个数示例
参考博客 :
【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
【组合数学】生成函数 ( 线性性质 | 乘积性质 )
【组合数学】生成函数 ( 移位性质 )
【组合数学】生成函数 ( 求和性质 )
【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 )
一、使用生成函数求解不定方程解个数示例
1 11 克砝码 2 22 个 ,
2 22 克砝码 1 11 个 ,
4 44 克砝码 2 22 个 ,
可以称出哪些重量 , 有多少方案个数 ;
砝码可以放在左右两侧
将生成函数的概念 , 推广到可以放负数次幂 , 放在左边是正数 , 不放是 0 00 , 放在右边是负数 ,
1 11 克的砝码 个数是 x 1 x_1x
1
个 , 取值范围是 − 2 ≤ x 1 ≤ 2 -2 \leq x_1 \leq 2−2≤x
1
≤2 , 可取值 − 2 , − 1 , 0 , 1 , 2 -2, -1, 0 , 1, 2−2,−1,0,1,2
2 22 克的砝码个数是 x 2 x_2x
2
个 , 取值范围是 − 1 ≤ x 2 ≤ 1 -1 \leq x_2 \leq 1−1≤x
2
≤1 , 可取值 − 1 , 0 , 1 -1, 0,1−1,0,1
4 44 克的砝码个数是 x 3 x_3x
3
个 , 取值范围是 − 2 ≤ x 3 ≤ 2 -2 \leq x_3 \leq 2−2≤x
3
≤2 , 可取值 − 2 , − 1 , 0 , 1 , 2 -2, -1, 0,1,2−2,−1,0,1,2
x 1 + 2 x 2 + 4 x 3 = r x_1 + 2x_2 + 4x_3 = rx
1
+2x
2
+4x
3
=r , 其中 r rr 代表可以称出的重量 ,
写出上述 , 带限制条件 , 并且带系数 的不定方程非负整数解的 生成函数 :
x 1 x_1x
1
项 , 带限制条件 , 没有系数 , 其 底是 y yy , 幂取值 0 , 1 , 2 0 , 1, 20,1,2 , 对应的生成函数项是 ( y − 2 + y − 1 + 1 + y + y 2 ) (y^{-2} + y^{-1} + 1 + y + y^2 )(y
−2
+y
−1
+1+y+y
2
)
x 2 x_2x
2
项 , 带限制条件 , 带系数 2 22 , 其 底是 y 2 y^2y
2
, 幂取值 0 , 1 0,10,1 , 对应生成函数项是 ( y 2 ) − 1 + ( y 2 ) 0 + ( y 2 ) 1 = y − 2 + 1 + y 2 (y^2)^{-1} + (y^2)^0 + (y^2)^1 = y^{-2} + 1+ y^2(y
2
)
−1
+(y
2
)
0
+(y
2
)
1
=y
−2
+1+y
2
x 3 x_3x
3
项 , 带限制条件 , 带系数 4 44 , 其 底是 y 4 y^4y
4
, 幂取值 0 , 1 , 2 0,1, 20,1,2 , 对应生成函数项是 ( y 4 ) − 2 + ( y 4 ) − 1 + ( y 4 ) 0 + ( y 4 ) 1 + ( y 4 ) 2 = y − 8 + y − 4 + 1 + y 4 + y 8 (y^4)^{-2} + (y^4)^{-1} + (y^4)^0 + (y^4)^1 + (y^4)^2 = y^{-8} + y^{-4} + 1+ y^4 + y^8(y
4
)
−2
+(y
4
)
−1
+(y
4
)
0
+(y
4
)
1
+(y
4
)
2
=y
−8
+y
−4
+1+y
4
+y
8
将上述三项乘起来 , 并展开 :
G ( x ) = ( y − 2 + y − 1 + 1 + y + y 2 ) ( y − 2 + 1 + y 2 ) ( y − 8 + y − 4 + 1 + y 4 + y 8 ) G(x) = ( y^{-2} + y^{-1} + 1 + y + y^2 ) (y^{-2} + 1+ y^2) (y^{-8} + y^{-4} + 1+ y^4 + y^8)G(x)=(y
−2
+y
−1
+1+y+y
2
)(y
−2
+1+y
2
)(y
−8
+y
−4
+1+y
4
+y
8
)
= 5 + 3 y + 4 y 2 + 3 y 3 + 5 y 4 + 3 y 5 + 4 y 6 + 3 y 7 + 4 y 8 + 2 y 9 + 2 y 10 + y 11 + y 12 \ \ \ \ \ \ \ \ \ \ =5 + 3y + 4y^2 + 3y^3 + 5y^4 + 3y^5 + 4y^6 + 3y^7 + 4y^8 + 2y^9 + 2y^{10} + y^{11} + y^{12} =5+3y+4y
2
+3y
3
+5y
4
+3y
5
+4y
6
+3y
7
+4y
8
+2y
9
+2y
10
+y
11
+y
12
上述展开后的 y yy 的次幂数是重量 , 系数是 方案个数 , 如 4 y 2 4y^24y
2
项表示 , 称出 2 22 克重量 , 有 4 44 个方案 ;
总体描述 :
1 11 项 : 表示 y 0 y^0y
0
, 称出 0 00 克 , 有 0 00 种方案 ;
3 y 3y3y 项 : 表示 3 y 1 3y^13y
1
, 称出 1 11 克 , 有 3 33 种方案 ;
4 y 2 4y^24y
2
项 : 表示 4 y 2 4y^24y
2
, 称出 2 22 克 , 有 4 44 种方案 ;
3 y 3 3y^33y
3
项 : 表示 3 y 3 3y^33y
3
, 称出 3 33 克 , 有 3 33 种方案 ;
5 y 4 5y^45y
4
项 : 表示 5 y 4 5y^45y
4
, 称出 4 44 克 , 有 5 55 种方案 ;
3 y 5 3y^53y
5
项 : 表示 3 y 5 3y^53y
5
, 称出 5 55 克 , 有 3 33 种方案 ;
4 y 6 4y^64y
6
项 : 表示 4 y 6 4y^64y
6
, 称出 6 66 克 , 有 4 44 种方案 ;
3 y 7 3y^73y
7
项 : 表示 3 y 7 3y^73y
7
, 称出 7 77 克 , 有 3 33 种方案 ;
4 y 8 4y^84y
8
项 : 表示 4 y 8 4y^84y
8
, 称出 8 88 克 , 有 4 44 种方案 ;
2 y 9 2y^92y
9
项 : 表示 2 y 9 2y^92y
9
, 称出 9 99 克 , 有 2 22 种方案 ;
2 y 10 2y^{10}2y
10
项 : 表示 2 y 10 2y^{10}2y
10
, 称出 10 1010 克 , 有 2 22 种方案 ;
y 11 y^{11}y
11
项 : 表示 y 11 y^{11}y
11
, 称出 11 1111 克 , 有 1 11 种方案 ;
y 12 y^{12}y
12
项 : 表示 y 12 y^{12}y
12
, 称出 12 1212 克 , 有 1 11 种方案 ;
