3

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?

user148664
  • 31
  • Would a lower bound be enough. What is the application?. The lower bound is $(m \times a1 \times a2 \times a3 \times\cdots an)$. Otherwise, it is pretty complicated – Satish Ramanathan May 08 '14 at 11:24

2 Answers2

3

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)$.

Marc van Leeuwen
  • 115,048
1

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\}$.

Rus May
  • 2,087
  • What is the faster way to find the sum of all the coefficients upto x^m?

    ie - coeff of x0 + coeff of x1 + coeff of x2 + ...coeff of xm?

     – asn Sep 11 '19 at 18:56