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

文章目录

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

参考博客 :

【组合数学】生成函数简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
【组合数学】生成函数 ( 线性性质 | 乘积性质 )
【组合数学】生成函数 ( 移位性质 )
【组合数学】生成函数 ( 求和性质 )
【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
【组合数学】生成函数 ( 使用生成函数求解多重集 r 组合数 )

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

不定方程的解个数 :

x_1 x_2 cdots x_k = r

x_i

为自然数 ;

之前通过组合对应的方法 , 已经解决 , 其解个数是

C(k r - 1 , r)

不定方程解的个数 , 推导过程参考 : 【组合数学】排列组合 ( 多重集组合数 | 所有元素重复度大于组合数 | 多重集组合数推导 1 分割线推导 | 多重集组合数推导 2 不定方程非负整数解个数推导 ) 二、多重集组合所有元素重复度大于组合数推导 2 ( 不定方程非负整数解个数推导 )

上述情况下 ,

x_i

的取值都是没有上限的 , 如果

x_i

取值受限 , 如

x_1

取值必须满足

2 leq x_1 leq 5

条件时 , 就不能使用上述公式进行计算 , 这里需要使用到生成函数求解 ;

1、带限制条件

x_1 x_2 cdots x_k = r

如果

x_i

取值受到约束 ,

l_i leq x_i leq n_i

, 则对应的生成函数项的

次幂值从

l_i

到

n_i

;

对应的生成函数项是

y^{l_i} y^{l_i 1} cdots y^{n_i}

完整的生成函数是 :

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} )

将上述生成函数结果乘出来 ,

y^r

前的系数 , 就是不定方程的解的个数 ;

2、带系数

p_1x_1 p_2x_2 cdots p_kx_k = r

x_i in N

, 非负整数解 , 对

x_i

不设置上限 ;

带系数的函数非负整数解 , 生成函数的项的基本的底是

y^{p_i}

, 幂的取值范围是

0 , 1, 2, cdots

每个生成函数项是

(y^{p_i})^0 (y^{p_i})^1 (y^{p_i})^2 (y^{p_i})^3 cdots

化简后的项是

1 y^{p_i} y^{2p_i} y^{3p_i} cdots

将所有的

项相乘 , 就是对应的生成函数 :

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})

该方程的非负整数解个数是

y^r

前的系数 ;

博客函数数学

0 人点赞