The sum of the works that took k elements from a set of n elements

Question

For a set S with elements n and an integer k . I need to find the sum of the products of all n to choose pairs k . That is, if S = {1,2,3,4} and k = 2 , then I'm looking for P = 1*2 + 1*3 + 1*4 + 2*3 + 2*4 +3*4 . Note that product pairs are a collection of elements k different elements from a collection of elements n . I can formulate a simple version of dynamic programming:

 P(n,k) = a_{n}P(n-1,k-1) + P(n-1,k) 

That is, take n-1 elements and select k-1 and add a_{n} , and also leave a_{n} . Is there any good theory to find a closed-form solution for the above problem? I'm a little lacking in advanced math, although programming worries me. I was able to withdraw the aforementioned DP, but could not go to the closed form, which, I hope, is!

Answer 1

I do not know if this is really useful, but it occurs to me that you are describing elementary symmetric polynomials .

Also, it looks like this document might come in handy:

Calculation of elementary symmetric polynomials with subpolynomial number of multiplications

Answer 2

Given n, k, how did you define them:

the number of products to be added # (n, k) is given by

(n, k) = C (n + k-1, k-1), where C (a, b) is a combinatorial function, i.e.

  a objects selected b at a time. 

In addition, # (n, k) = k * # (n-1, k) - (n-1) * # (n, k-1).