参考博客 :

• 【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关 | 与多项式系数相关 )
• 【组合数学】生成函数 ( 线性性质 | 乘积性质 )
• 【组合数学】生成函数 ( 移位性质 )
• 【组合数学】生成函数 ( 求和性质 )
• 【组合数学】生成函数 ( 换元性质 | 求导性质 | 积分性质 )
• 【组合数学】生成函数 ( 性质总结 | 重要的生成函数 ) ★
• 【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
• 【组合数学】生成函数 ( 生成函数应用场景 | 使用生成函数求解递推方程 )
• 【组合数学】生成函数 ( 使用生成函数求解多重集 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\le x_1\le 5$ 条件时 , 就不能使用上述公式进行计算 , 这里需要 使用到生成函数求解 ;

1、带限制条件

$x_1+x_2+\cdots +x_k=r$

如果 $x_i$ 取值受到约束 , $l_i\le x_i\le n_i$ , 则对应的 生成函数项的 $y$ 次幂值从 $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_1{x}_1+p_2{x}_2+\cdots +p_k{x}_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$

将所有的 $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 })$

该方程的非负整数解个数是 $y^r$ 前的系数 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/109353385