從一組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）。