1500字范文 > 【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )

【组合数学】生成函数 ( 使用生成函数求解不定方程解个数 )

时间：2022-11-22 02:05:49

文章目录

一、使用生成函数求解不定方程解个数1、带限制条件2、带系数

参考博客 :

一、使用生成函数求解不定方程解个数

不定方程的解个数 :

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 前的系数 ;

本内容不代表本网观点和政治立场，如有侵犯你的权益请联系我们处理。

网友评论

网友评论仅供其表达个人看法，并不表明网站立场。