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