给定一个有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,但无法得出我希望得到的闭合形式!