文章目录
一、生成函数应用场景
二、使用生成函数求解递推方程
参考博客 :
【组合数学】生成函数 简要介绍 ( 生成函数定义 | 牛顿二项式系数 | 常用的生成函数 | 与常数相关 | 与二项式系数相关...生成函数 ( 性质总结 | 重要的生成函数 ) ★
【组合数学】生成函数 ( 生成函数示例 | 给定通项公式求生成函数 | 给定生成函数求通项公式 )
一、生成函数应用场景
----
生成函数应用场景 :
求解递推方程...+ r - 1, r)
, 如果
r
大于重复度 , 就需要使用生成函数进行求解 ;
不定方程的解个数 , 之前只能求解 没有约束的情况 , 如果对变量有约束 , 如
x_1
只能在某个区间取值..., 这种情况下 , 就必须使用生成函数进行求解 ;
整数拆分 , 将一个正数拆分多若干整数之和 , 拆分方案个数 , 也可以通过生成函数进行计算 ;
回顾多重集排列组合 :
可重复的元素 , 有序的选取..., 非全排列
k^r , \ \ r\leq n_i
可重复的元素 , 无序的选取 , 对应 多重集的组合 ;
N= C(k + r - 1, r)
二、使用生成函数求解递推方程
----
递推方程