技术咨询:求分拆为2、5或7的可重复分拆生成函数
分拆为2、5或7且部分可重复的生成函数
嘿,我来帮你理清楚这个生成函数的问题~
首先,咱们先回忆一下可重复分拆的生成函数基本构造逻辑:对于一个允许重复使用的正整数k,它对应的生成函数是所有可能使用次数(0次、1次、2次……)的项的和,也就是:1 + x^k + x^(2k) + x^(3k) + ...
这是一个无穷等比级数,收敛时可以简化为 1/(1 - x^k)。
回到你的问题,我们需要分别构造每个允许部分的生成函数,再把它们相乘(因为分拆中不同部分的选择是独立的,生成函数的乘法对应组合的叠加):
- 对于可重复使用的部分2,生成函数是
1/(1 - x²) - 对于可重复使用的部分5,生成函数是
1/(1 - x⁵) - 对于可重复使用的部分7,生成函数是
1/(1 - x⁷)
把这三个生成函数相乘,就得到了分拆为2、5或7且部分可重复的生成函数:G(x) = 1/[(1 - x²)(1 - x⁵)(1 - x⁷)]
如果你想验证的话,展开这个生成函数后,xn的系数就是把n拆成若干个2、5、7之和的方式数,比如x9的系数是2(对应分拆方式:2+7 和 2+2+5),完全符合预期。
内容的提问来源于stack exchange,提问作者John
相关产品推荐
相关产品推荐

