algorithm - 程序可以用来简化代数表达式吗？

Question

我们知道1+2+...+n等于n(n+1)/2。

但是，如果我们事先不知道，我们能否以编程方式获得相同的结果？

关于为什么我有这样的问题。

考虑一个更复杂的情况：

X1+X2+...+Xk=n，其中 Xi 是整数且 >= 0。

的期望是X1^2+...Xk^2什么？

结果一目了然，一旦我们计算出期望的（详细）数学表示，我们将希望将其提供给程序以减少代数X1^2+...Xk^2

Answer 1

也许您正在考虑计算机代数系统(CAS)？WolframAlpha是一个免费的在线软件，它在后端使用 Mathematica（一个非常强大的 CAS 系统）。在这里你可以看到它计算/简化你的表达式：WolframAlpha。

您的示例只是平方和，它有一个非常简单的显式公式：n(n+1)(2n+1)/6. 更一般地，您可以使用Faulhaber 公式计算Sum of n^p.

Answer 2

好的，首先是关于问题的数学部分的一些建议，然后是关于软件开发的一些建议。

Marko Petkov·sek、Herbert S. Wilf 和 Doron Zeilberger的电子书“A=B”处理了比多项式更困难的求和问题（或显示没有解）。伊恩·万利斯 (Ian Wanless)的书评值得快速阅读。电子书可免费下载，但可以从亚马逊等购买装订本。

2004 年的翻译。Greene 和 Wilf的 AMS 论文Closed Form Summation of C -finite Sequences也可在线获得。

一般来说，你需要一些基本的 CAS 软件来实现这些算法，听起来目标是自己开发这样的软件。我建议研究一些开源 CAS（计算机代数软件）包，例如Maxima或Axiom，以了解所涉及的范围。当然，目标狭窄的应用程序很可能只使用这些相当成熟和高端软件包实现的一小部分，但考虑到问题的当前措辞，我认为我无法为您指明一条更直接的路径.

如果表达式的“预期”包含在您的项目范围内，那么在单纯的代数操作之上会出现许多复杂情况。一个人当然需要能够指定概率密度函数来支持期望值，并且可能需要一些集成软件（尽管可能限制参数化分布的选择可能会导致查找这些分布的矩的简化问题）。我确实认为这是一个特别好的应用程序，因为看似简单的随机变量表达式（总和，最大值/最小值）可能会导致对案例的噩梦般的考虑，非常适合计算机的耐心。

Answer 3

编辑，由于您最近对帖子的澄清。

除非您拥有整个博士团队并花费数年时间，否则您将无法摆脱手工制作的解决方案。我能给您的最佳建议是购买Mathematica（或其他）许可证并将其与您的程序接口。

如果您是 Lisp 程序员，使用 Maxima 是另一种潜在的（免费的）解决方案。

如果你想了解求和算法的最新技术，这篇论文是一个好的开始。

---

X1+X2+...+Xk=n，其中 Xi 是整数且 >= 0。

X1^2+...Xk^2 的期望是什么？

这类问题占据了很多人的纸上谈兵。

让我们取 k = 2。然后 X_1 + X_2 = n 给出 X_2 = n - X_1。

所以要计算的期望是E = X_1^2 + (n - X_1)^2 = 2 X_1^2 -2n X_1 + n^2。

这读

E = sum(p_k * (2 * k^2 - 2 * n * k + n^2), k = 0..infinity)

哪里p_k = Prob(X_1 = k)。这种总和，取决于p_k，通常很难计算。我想说这个问题比计算封闭形式的积分还要困难（没有软件完全实现可用的——但无法确定的——Risch 算法）。

为了说服自己，例如。p_k = 1 / (log(k) * k^4).

为其找到一个公式（或公式生成器）至少是一个非常困难的研究问题。