文章目录
一、使用生成函数求解不定方程解个数1、带限制条件2、带系数参考博客 :
【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )【组合数学】生成函数 ( 线性性质 | 乘积性质 )【组合数学】生成函数 ( 移位性质 )【组合数学】生成函数 ( 求和性质 )【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )
一、使用生成函数求解不定方程解个数
不定方程的解个数 :
x1+x2+⋯+xk=rx_1 + x_2 + \cdots + x_k = rx1+x2+⋯+xk=r
xix_ixi 为自然数 ;
之前通过组合对应的方法 , 已经解决 , 其解个数是 C(k+r−1,r)C(k + r - 1 , r)C(k+r−1,r)
不定方程解的个数 , 推导过程参考 :【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数 推导 1 分割线推导 | 多重集组合数 推导 2 不定方程非负整数解个数推导 ) 二、多重集组合 所有元素重复度大于组合数 推导 2 ( 不定方程非负整数解个数推导 )
上述情况下 , xix_ixi 的取值都是没有上限的 , 如果 xix_ixi 取值受限 , 如 x1x_1x1 取值必须满足 2≤x1≤52 \leq x_1 \leq 52≤x1≤5 条件时 , 就不能使用上述公式进行计算 , 这里需要 使用到生成函数求解 ;
1、带限制条件
x1+x2+⋯+xk=rx_1 + x_2 + \cdots + x_k = rx1+x2+⋯+xk=r
如果 xix_ixi 取值受到约束 , li≤xi≤nil_i \leq x_i \leq n_ili≤xi≤ni , 则对应的 生成函数项的 yyy 次幂值从 lil_ili 到 nin_ini ;
对应的生成函数项是 yli+yli+1+⋯+yniy^{l_i} + y^{l_i + 1} + \cdots + y^{n_i}yli+yli+1+⋯+yni
完整的生成函数是 :
G(y)=(yl1+yl1+1+⋯+yn1)(yl2+yl2+1+⋯+yn2)⋯(ylk+ylk+1+⋯+ynk)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)=(yl1+yl1+1+⋯+yn1)(yl2+yl2+1+⋯+yn2)⋯(ylk+ylk+1+⋯+ynk)
将上述生成函数结果乘出来 , yry^ryr 前的系数 , 就是不定方程 的解的个数 ;
2、带系数
p1x1+p2x2+⋯+pkxk=rp_1x_1 + p_2x_2 + \cdots + p_kx_k = rp1x1+p2x2+⋯+pkxk=r
xi∈Nx_i \in Nxi∈N , 非负整数解 , 对 xix_ixi 不设置上限 ;
带系数的函数非负整数解 , 生成函数的项的基本的 底是 ypiy^{p_i}ypi , 幂的取值范围是 0,1,2,⋯0 , 1, 2, \cdots0,1,2,⋯ ,
每个生成函数项是 (ypi)0+(ypi)1+(ypi)2+(ypi)3+⋯(y^{p_i})^0 + (y^{p_i})^1 + (y^{p_i})^2 + (y^{p_i})^3 + \cdots(ypi)0+(ypi)1+(ypi)2+(ypi)3+⋯ ,
化简后的项是 1+ypi+y2pi+y3pi+⋯1 +y^{p_i} + y^{2p_i} + y^{3p_i} + \cdots1+ypi+y2pi+y3pi+⋯
将所有的 kkk 项相乘 , 就是对应的生成函数 :
G(y)=(1+yp1+y2p1+y3p1+⋯)(1+yp2+y2p2+y3p2+⋯)⋯(1+ypk+y2pk+y3pk+⋯)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+yp1+y2p1+y3p1+⋯)(1+yp2+y2p2+y3p2+⋯)⋯(1+ypk+y2pk+y3pk+⋯)
该方程的非负整数解个数是 yry^ryr 前的系数 ;