文章目录
一、使用生成函数求解不定方程解个数
1、带限制条件
2、带系数
参考博客 :
【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
【组合数学】生成函数 ( 线性性质 | 乘积性质 )
【组合数学】生成函数 ( 移位性质 )
【组合数学】生成函数 ( 求和性质 )
【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
一、使用生成函数求解不定方程解个数
不定方程的解个数 :
x 1 + x 2 + ⋯ + x k = r x_1 + x_2 + \cdots + x_k = rx
1
+x
2
+⋯+x
k
=r
x i x_ix
i
为自然数 ;
之前通过组合对应的方法 , 已经解决 , 其解个数是 C ( k + r − 1 , r ) C(k + r - 1 , r)C(k+r−1,r)
不定方程解的个数 , 推导过程参考 : 【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数 推导 1 分割线推导 | 多重集组合数 推导 2 不定方程非负整数解个数推导 ) 二、多重集组合 所有元素重复度大于组合数 推导 2 ( 不定方程非负整数解个数推导 )
上述情况下 , x i x_ix
i
的取值都是没有上限的 , 如果 x i x_ix
i
取值受限 , 如 x 1 x_1x
1
取值必须满足 2 ≤ x 1 ≤ 5 2 \leq x_1 \leq 52≤x
1
≤5 条件时 , 就不能使用上述公式进行计算 , 这里需要 使用到生成函数求解 ;
1、带限制条件
x 1 + x 2 + ⋯ + x k = r x_1 + x_2 + \cdots + x_k = rx
1
+x
2
+⋯+x
k
=r
如果 x i x_ix
i
取值受到约束 , l i ≤ x i ≤ n i l_i \leq x_i \leq n_il
i
≤x
i
≤n
i
, 则对应的 生成函数项的 y yy 次幂值从 l i l_il
i
到 n i n_in
i
;
对应的生成函数项是 y l i + y l i + 1 + ⋯ + y n i y^{l_i} + y^{l_i + 1} + \cdots + y^{n_i}y
l
i
+y
l
i
+1
+⋯+y
n
i
完整的生成函数是 :
G ( y ) = ( y l 1 + y l 1 + 1 + ⋯ + y n 1 ) ( y l 2 + y l 2 + 1 + ⋯ + y n 2 ) ⋯ ( y l k + y l k + 1 + ⋯ + y n k ) G(y) = ( y^{l_1} + y^{l_1+1} + \cdots + y^{n_1} )( y^{l_2} + y^{l_2+1} + \cdots + y^{n_2} ) \cdots ( y^{l_k} + y^{l_k+1} + \cdots + y^{n_k} )G(y)=(y
l
1
+y
l
1
+1
+⋯+y
n
1
)(y
l
2
+y
l
2
+1
+⋯+y
n
2
)⋯(y
l
k
+y
l
k
+1
+⋯+y
n
k
)
将上述生成函数结果乘出来 , y r y^ry
r
前的系数 , 就是不定方程 的解的个数 ;
2、带系数
p 1 x 1 + p 2 x 2 + ⋯ + p k x k = r p_1x_1 + p_2x_2 + \cdots + p_kx_k = rp
1
x
1
+p
2
x
2
+⋯+p
k
x
k
=r
x i ∈ N x_i \in Nx
i
∈N , 非负整数解 , 对 x i x_ix
i
不设置上限 ;
带系数的函数非负整数解 , 生成函数的项的基本的 底是 y p i y^{p_i}y
p
i
, 幂的取值范围是 0 , 1 , 2 , ⋯ 0 , 1, 2, \cdots0,1,2,⋯ ,
每个生成函数项是 ( y p i ) 0 + ( y p i ) 1 + ( y p i ) 2 + ( y p i ) 3 + ⋯ (y^{p_i})^0 + (y^{p_i})^1 + (y^{p_i})^2 + (y^{p_i})^3 + \cdots(y
p
i
)
0
+(y
p
i
)
1
+(y
p
i
)
2
+(y
p
i
)
3
+⋯ ,
化简后的项是 1 + y p i + y 2 p i + y 3 p i + ⋯ 1 +y^{p_i} + y^{2p_i} + y^{3p_i} + \cdots1+y
p
i
+y
2p
i
+y
3p
i
+⋯
将所有的 k kk 项相乘 , 就是对应的生成函数 :
G ( y ) = ( 1 + y p 1 + y 2 p 1 + y 3 p 1 + ⋯ ) ( 1 + y p 2 + y 2 p 2 + y 3 p 2 + ⋯ ) ⋯ ( 1 + y p k + y 2 p k + y 3 p k + ⋯ ) G(y)=(1+y^{p_1} + y^{2p_1} + y^{3p_1 + \cdots})(1+y^{p_2} + y^{2p_2} + y^{3p_2 + \cdots}) \cdots (1+y^{p_k} + y^{2p_k} + y^{3p_k + \cdots})G(y)=(1+y
p
1
+y
2p
1
+y
3p
1
+⋯
)(1+y
p
2
+y
2p
2
+y
3p
2
+⋯
)⋯(1+y
p
k
+y
2p
k
+y
3p
k
+⋯
)
该方程的非负整数解个数是 y r y^ry
r
前的系数 ;