5

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!

4

2 回答 2

5

我不知道它是否真的有用，但我突然想到您正在描述基本对称多项式。

此外，本文似乎对您有用：

计算具有次多项式乘法数的基本对称多项式

于 2011-11-16T07:53:22.540 回答
0

给定 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)。

于 2013-04-01T16:53:52.373 回答