文章目录
一、生成函数应用场景
二、使用生成函数求解递推方程
参考博客 :
【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关...----
生成函数应用场景 :
求解递推方程
多重集
r
组合计数
不定方程解个数
整数拆分
多重集
r
组合计数 , 之前 只能计数特殊情况下的组合数 , 也就是选取数
r
小于多重集每一项的重复度..., 才有 组合数
N= C(k + r - 1, r)
, 如果
r
大于重复度 , 就需要使用生成函数进行求解 ;
不定方程的解个数 , 之前只能求解 没有约束的情况 , 如果对变量有约束..., 非全排列
k^r , \ \ r\leq n_i
可重复的元素 , 无序的选取 , 对应 多重集的组合 ;
N= C(k + r - 1, r)
二、使用生成函数求解递推方程
----
递推方程...cdot 2^n - 4 \cdot 3^n
基本思路 : 有原来的递推方程 , 导出关于生成函数的递推方程 ;