combinatorics - 从一组 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 .请注意，产品对构成了集合——取 k来自一组 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