IDEA激活码
文章目录
- 一、使用生成函数求解不定方程解个数示例
参考博客 :
- 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
- 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
- 【组合数学】生成函数 ( 移位性质 )
- 【组合数学】生成函数 ( 求和性质 )
- 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
- 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
- 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
- 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
- 【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
- 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )
一、使用生成函数求解不定方程解个数示例
1
1
1 克砝码
2
2
2 个 ,
2
2
2 克砝码
1
1
1 个 ,
4
4
4 克砝码
2
2
2 个 ,
可以称出哪些重量 , 有多少方案个数 ;
1
1
1 克的砝码 个数是
x
1
x_1
x1 个 , 取值范围是
0
≤
x
1
≤
2
0 \leq x_1 \leq 2
0≤x1≤2 , 可取值
0
,
1
,
2
0 , 1, 2
0,1,2
2
2
2 克的砝码个数是
x
2
x_2
x2 个 , 取值范围是
0
≤
x
2
≤
1
0 \leq x_2 \leq 1
0≤x2≤1 , 可取值
0
,
1
0,1
0,1
4
4
4 克的砝码个数是
x
3
x_3
x3 个 , 取值范围是
0
≤
x
3
≤
2
0 \leq x_3 \leq 2
0≤x3≤2 , 可取值
0
,
1
,
2
0,1,2
0,1,2
x
1
+
2
x
2
+
4
x
3
=
r
x_1 + 2x_2 + 4x_3 = r
x1+2x2+4x3=r , 其中
r
r
r 代表可以称出的重量 ,
写出上述 , 带限制条件 , 并且带系数 的不定方程非负整数解的 生成函数 :
x
1
x_1
x1 项 , 带限制条件 , 没有系数 , 其 底是
y
y
y , 幂取值
0
,
1
,
2
0 , 1, 2
0,1,2 , 对应的生成函数项是
(
1
+
y
+
y
2
)
( 1 + y + y^2 )
(1+y+y2)
x
2
x_2
x2 项 , 带限制条件 , 带系数
2
2
2 , 其 底是
y
2
y^2
y2 , 幂取值
0
,
1
0,1
0,1 , 对应生成函数项是
(
y
2
)
0
+
(
y
2
)
1
=
1
+
y
2
(y^2)^0 + (y^2)^1 = 1+ y^2
(y2)0+(y2)1=1+y2
x
3
x_3
x3 项 , 带限制条件 , 带系数
4
4
4 , 其 底是
y
4
y^4
y4 , 幂取值
0
,
1
,
2
0,1, 2
0,1,2 , 对应生成函数项是
(
y
4
)
0
+
(
y
4
)
1
+
(
y
4
)
2
=
1
+
y
4
+
y
8
(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
+
y
2
)
(
1
+
y
2
)
(
1
+
y
4
+
y
8
)
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
+
2
y
2
+
y
3
+
2
y
4
+
y
5
+
2
y
6
+
y
7
+
2
y
8
+
y
9
+
2
y
10
+
y
11
+
y
12
\ \ \ \ \ \ \ \ \ \ =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
上述展开后的
y
y
y 的次幂数是重量 , 系数是 方案个数 , 如
2
y
8
2y^8
2y8 项表示 , 称出
8
8
8 克重量 , 有
2
2
2 个方案 ;
总体描述 :
-
1
1
1 项 : 表示y
0
y^0
y0 , 称出0
0
0 克 , 有0
0
0 种方案 ; -
y
y
y 项 : 表示y
1
y^1
y1 , 称出1
1
1 克 , 有1
1
1 种方案 ; -
2
y
2
2y^2
2y2 项 : 表示2
y
2
2y^2
2y2 , 称出2
2
2 克 , 有2
2
2 种方案 ; -
y
3
y^3
y3 项 : 表示y
3
y^3
y3 , 称出3
3
3 克 , 有1
1
1 种方案 ; -
2
y
4
2y^4
2y4 项 : 表示2
y
4
2y^4
2y4 , 称出4
4
4 克 , 有2
2
2 种方案 ; -
y
5
y^5
y5 项 : 表示y
5
y^5
y5 , 称出5
5
5 克 , 有1
1
1 种方案 ; -
2
y
6
2y^6
2y6 项 : 表示2
y
6
2y^6
2y6 , 称出6
6
6 克 , 有2
2
2 种方案 ; -
y
7
y^7
y7 项 : 表示y
7
y^7
y7 , 称出7
7
7 克 , 有1
1
1 种方案 ; -
2
y
8
2y^8
2y8 项 : 表示2
y
8
2y^8
2y8 , 称出8
8
8 克 , 有2
2
2 种方案 ; -
y
9
y^9
y9 项 : 表示y
9
y^9
y9 , 称出9
9
9 克 , 有1
1
1 种方案 ; -
2
y
10
2y^{10}
2y10 项 : 表示2
y
10
2y^{10}
2y10 , 称出10
10
10 克 , 有2
2
2 种方案 ; -
y
11
y^{11}
y11 项 : 表示y
11
y^{11}
y11 , 称出11
11
11 克 , 有1
1
1 种方案 ; -
y
12
y^{12}
y12 项 : 表示y
12
y^{12}
y12 , 称出12
12
12 克 , 有1
1
1 种方案 ;
