math - n 次多项式生成

Question

我基本上是在寻找一个求和函数，该函数将在给定变量数量和次数的情况下计算多项式。

例子

2 Variables; 2 Degrees:

x^2+y^2+x*y+x+y+1

谢谢。

Answer 1

参见 Knuth 计算机编程艺术，第 1 卷。 4，分册 3 的全面解答。

简短回答:生成 n 个变量的所有多项式表达式，正好 d 次就足够了。然后，对于您的问题，您可以将度数≤d 的答案放在一起，或者添加一个虚拟变量“1”。

因此，生成所有度数恰好为 d 的表达式的问题只是生成所有有序分区(即，x₁ + ... + x_{n< 的所有非负整数解之一)/sub> = d)，这可以通过简单的回溯算法来完成。 ("深度优先搜索")}