san*_*ket 5 dynamic-programming combinatorics discrete-mathematics polynomial-math
给定一个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，但无法继续到我希望有的封闭形式！