Sum of multiplication of all combination of m element from an array of n elements

Suppose I have an array {1, 2, 3, 4} and m = 3. I need to find:

1*2*3 + 1*2*4 + 1*3*4 + 2*3*4

i.e Sum of multiplication of all combination of m element from an array of n elements.

One of the solution possible is to find all combination and then solving it but that would be O(nCm) solution. Is there any faster solution?

Solution 1:

What you are asking for is the value of the elementary symmetric polynomial $e_m$ with as arguments the elements $a_1,\ldots,a_n$ of your array. The traditional occurrence of these symmetric polynomials is the coefficient of $X^{n-m}$ the polynomial $(X+a_1)(X+a_2)\ldots(X+a_n)$ with roots $-a_1,-a_2,\ldots,-a_n$. You can make it a bit nicer by moving the $X$ to the other term: the coefficient of $X^n$ in the product $(1+a_1X)(1+a_2X)\ldots(1+a_nX)$ is also $e_m[a_1,a_2,\ldots,a_n]$.

The number of algebraic operations needed to compute this polynomial product is $O(n^2)$.

Solution 2:

In the generating-function view of the world, your sum is the coefficient of $x^m$ in $(1+1x)(1+2x)(1+3x)\dots(1+nx)$. I suspect this will lead to a fairly concrete form for the sum. In any case, it is quicker to calculate than all the $m$-subsets of $\{1,2,\dots,n\}$.