从 n 个元素的集合中取出 k 个元素的乘积之和
给定一个包含 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，但无法继续到我希望有的封闭形式！
Given a set S with n elements, and an integer k. I need to find the sum of products of all n choose k pairs. That is, if S = {1,2,3,4} and k = 2, then I am looking for P = 1*2 + 1*3 + 1*4 + 2*3 + 2*4 +3*4. Note that product-pairs constitute the set -- taking k distinct elements from a set of n elements. I can formulate a simple dynamic programming version of this:
P(n,k) = a_{n}P(n-1,k-1) + P(n-1,k)
That is, take n-1 elements and choose k-1 and add a_{n} as well as leave out a_{n}. Is there some nice theory to find a closed form solution to the above problem? I am a bit lacking on advanced maths, though programming excites me. I was able to derive the aforementioned DP but could not proceed to a closed form which I hope there is!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我不知道它是否真的有帮助，但我想到你正在描述基本对称多项式。
此外，看来本文可能对您有用：
使用次多项式乘法计算初等对称多项式
I do not know if it is actually helpful, but it occurs to me that you are describing elementary symmetric polynomials.
Further, it appears that this paper may be of use to you:
Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications
给定您所定义的 n、k：
要求和的乘积数量 #(n,k) 由
(n,k) = C(n+k-1, k-1) 给出，其中 C(a, b) 是组合函数，即
#(n,k) = k*#(n-1,k) - (n-1)*#(n,k-1)。
Given n, k as you have defined them:
the number of products to be summed #(n,k) is given by
(n,k) = C(n+k-1, k-1), where C(a,b) is the combinatoric function, ie,
Furthermore, #(n,k) = k*#(n-1,k) - (n-1)*#(n,k-1).