文章目录

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

参考博客 :

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

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

---

$1$ 克砝码 $2$ 个 ,
$2$ 克砝码 $1$ 个 ,
$4$ 克砝码 $2$ 个 ,
可以称出哪些重量 , 有多少方案个数 ;

砝码可以放在左右两侧

将生成函数的概念 , 推广到可以放负数次幂 , 放在左边是正数 , 不放是 $0$ , 放在右边是负数 ,

$1$ 克的砝码 个数是 $x_1$ 个 , 取值范围是 $-2\le x_1\le 2$ , 可取值 $-2,-1,0,1,2$

$2$ 克的砝码个数是 $x_2$ 个 , 取值范围是 $-1\le x_2\le 1$ , 可取值 $-1,0,1$

$4$ 克的砝码个数是 $x_3$ 个 , 取值范围是 $-2\le x_3\le 2$ , 可取值 $-2,-1,0,1,2$

$x_1+2x_2+4x_3=r$ , 其中 $r$ 代表可以称出的重量 ,

写出上述 , 带限制条件 , 并且带系数 的不定方程非负整数解的 生成函数 :

$x_1$ 项 , 带限制条件 , 没有系数 , 其 底是 $y$ , 幂取值 $0,1,2$ , 对应的生成函数项是 $(y^{-2}+y^{-1}+1+y+y^2)$

$x_2$ 项 , 带限制条件 , 带系数 $2$ , 其 底是 $y^2$ , 幂取值 $0,1$ , 对应生成函数项是 $(y^2{)}^{-1}+(y^2{)}^0+(y^2{)}^1=y^{-2}+1+y^2$

$x_3$ 项 , 带限制条件 , 带系数 $4$ , 其 底是 $y^4$ , 幂取值 $0,1,2$ , 对应生成函数项是 $(y^4{)}^{-2}+(y^4{)}^{-1}+(y^4{)}^0+(y^4{)}^1+(y^4{)}^2=y^{-8}+y^{-4}+1+y^4+y^8$

将上述三项乘起来 , 并展开 :

$G(x)=(y^{-2}+y^{-1}+1+y+y^2)(y^{-2}+1+y^2)(y^{-8}+y^{-4}+1+y^4+y^8)$

$=5+3y+4y^2+3y^3+5y^4+3y^5+4y^6+3y^7+4y^8+2y^9+2y^{10}+y^{11}+y^{12}$

上述展开后的 $y$ 的次幂数是重量 , 系数是 方案个数 , 如 $4y^2$ 项表示 , 称出 $2$ 克重量 , 有 $4$ 个方案 ;

总体描述 :

• $1$ 项 : 表示 $y^0$ , 称出 $0$ 克 , 有 $0$ 种方案 ;
• $3y$ 项 : 表示 $3y^1$ , 称出 $1$ 克 , 有 $3$ 种方案 ;
• $4y^2$ 项 : 表示 $4y^2$ , 称出 $2$ 克 , 有 $4$ 种方案 ;
• $3y^3$ 项 : 表示 $3y^3$ , 称出 $3$ 克 , 有 $3$ 种方案 ;
• $5y^4$ 项 : 表示 $5y^4$ , 称出 $4$ 克 , 有 $5$ 种方案 ;
• $3y^5$ 项 : 表示 $3y^5$ , 称出 $5$ 克 , 有 $3$ 种方案 ;
• $4y^6$ 项 : 表示 $4y^6$ , 称出 $6$ 克 , 有 $4$ 种方案 ;
• $3y^7$ 项 : 表示 $3y^7$ , 称出 $7$ 克 , 有 $3$ 种方案 ;
• $4y^8$ 项 : 表示 $4y^8$ , 称出 $8$ 克 , 有 $4$ 种方案 ;
• $2y^9$ 项 : 表示 $2y^9$ , 称出 $9$ 克 , 有 $2$ 种方案 ;
• $2y^{10}$ 项 : 表示 $2y^{10}$ , 称出 $10$ 克 , 有 $2$ 种方案 ;
• $y^{11}$ 项 : 表示 $y^{11}$ , 称出 $11$ 克 , 有 $1$ 种方案 ;
• $y^{12}$ 项 : 表示 $y^{12}$ , 称出 $12$ 克 , 有 $1$ 种方案 ;

总结

以上是生活随笔为你收集整理的【组合数学】生成函数 ( 使用生成函数求解不定方程解个数示例 2 | 扩展到整数解 )的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。