algorithm - 泰勒(麦克劳林)级数的高效生成

Question

考虑函数
y=1/((1-x^5)(1-x^7)(1-x^11))

WolframAlpha 在几秒钟内计算出 MacLaurin 级数展开的前 1000 个元素:
https://www.wolframalpha.com/input/?i=maclaurin+series+1%2F%28%281-x%5E5%29%281-x%5E7%29%281-x%5E11%29%29

出于好奇，我编写了一个非常简单的 java 程序来使用 BigInteger 对多项式系数执行相同的操作。在伪代码中它会是这样的:

BigInt next=1;
BigInt factorial=1;
while(true){
   function=function.differentiate();
   factorial*=++next;
   print("Next coefficient is: " + function(0)/factorial);
}

此程序在计算前七个左右的系数后因 java.lang.outofmemory 异常而崩溃，因为分数的分子和分母变成了非常长的多项式。假设我的代码效率低下，但 Wolfram 似乎仍然没有使用他们在第一年微积分课上向您展示的相同技术。
问题是:Wolfram 使用什么？

相比之下，Wolfram 计算同一个函数的十阶导数比计算多项式的前 1000 项所花的时间要多得多，如果天真地完成前 1000 项，则需要对函数进行 1000 次微分。
https://www.wolframalpha.com/input/?i=tenth+derivative+1%2F%28%281-x%5E5%29%281-x%5E7%29%281-x%5E11%29%29

Answer 1

tl;dr:x^N 的系数是仅使用 5、7 和 11 划分 N 的方式的数量。

我不确定 Wolfram 是如何做到的，但是对于这个函数，可以更有效地计算系数(使用您在微积分第一年末会看到的技术)。作为幂级数，1/(1-x)=∑_k=0^∞ x^k。但是我们可以用 xⁿ 替换 x，并且关系仍然成立。这意味着
1/((1-x⁵)(1-x⁷)(1-x¹¹)) = (∑_{k =0}^∞x^5k)(∑_k=0^∞x^7k)(∑_k=0^∞x^11k)

将其相乘会很痛苦。但是所有的系数都是 1，所以我们只需要看指数，它们加在一起。例如Wolfram显示x⁴⁰的系数为4，即来自(x^5·1)(x^7·5) (x^0·11)+(x^5·0)(x^7·1)(x^11·3)+(x^5·3)(x^7·2)(x^11·1)+(x^{5 ·8})(x^7·0)(x^11·0).

但如果我们只需要添加指数，那么我们就不需要关心系数或变量 x。最后，x^N 的系数是 N 可以写成 5s、7s 和 11s 之和的方式数。这是分区问题的限制版本，但同样的想法仍然成立。特别是，动态规划方法将能够计算线性时间和空间中的系数。