从n个元素的集合中取k个元素进行乘积求和

Question

给定一个有n个元素的集合S和一个整数k。我需要找到所有n选k对的积的总和。也就是说，如果S = {1,2,3,4}且k = 2，则我要找到P = 1*2 + 1*3 + 1*4 + 2*3 + 2*4 + 3*4。注意，积对构成集合——从n个元素的集合中取k个不同的元素。我可以制定一个简单的动态规划版本：

P(n,k) = a_{n}P(n-1,k-1) + P(n-1,k)

也就是说，取n-1个元素，选择k-1个并添加a_{n}，或者不添加a_{n}。是否有一些好的理论来找到上述问题的闭合形式解决方案？虽然编程让我兴奋，但我在高级数学方面有些欠缺。我能够推导出上述DP，但无法得出我希望得到的闭合形式！

- sanket

---

我认为这是一个有趣的问题，但也许更适合在数学领域进行讨论。在我看来，如果没有对集合元素的了解，那么闭合形式就是简单的总和。我认为这是定义上的。如果你正在寻求一种更有效的计算总和的方法，我想不出比你自己的更好的方法了。 - Mr.Wizard

Answer 1

我不确定这是否有帮助，但在我看来，您所描述的是 基本对称多项式。

此外，这篇论文可能对您有用：

使用次多项式个数计算基本对称多项式

- Mr.Wizard

Answer 2

假设你已经定义了n和k：

要求和的产品数量#(n,k)由以下公式给出：

(n,k) = C(n+k-1, k-1)，其中C(a,b)是组合函数，即

     a objects selected b at a time. 

此外， #(n,k) = k*#(n-1,k) - (n-1)*#(n,k-1)。

- jim farned