从一组n个元素中取出k个元素的产品总和

Question

给定一组S与n个元素和整数k。我需要找到所有产品的总和n选择k双。也就是说，如果S = {1,2,3,4} and k = 2，那么我正在寻找P = 1*2 + 1*3 + 1*4 + 2*3 + 2*4 +3*4。请注意，产品对构成了一组 - 从一组n元素中取出不同的元素。我可以制定这样一个简单的动态规划版本：

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

也就是说，采取n-1元素，并选择k-1，并添加a_{n}以及离开了a_{n}。是否有一些很好的理论来找到上述问题的封闭解决方案？虽然编程让我兴奋，但我对高级数学有点欠缺。我能够得出上述DP，但无法进入我希望的封闭形式！

Answer 1

我不知道它是否真的有帮助，但是我想你是在描述elementary symmetric polynomials。

而且，看来这纸可能对你有帮助：

Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications

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）。