Sum of products of K numbers taken from N numbers in closed form

1.1k Views Asked by At

Let's say i have 5 numbers, $A,B,C,D,E$. I want to know the sum of all the possible products of some or all of these numbers each taken at most once. Instead of a lot of multiplications and additions i can just calculate $(A+1)(B+1)(C+1)(D+1)(E+1) - 1$ . This is just 6 additions and 4 multiplications. Great. But what if i want the sum of all the possible products of, say, exactly 2 or 4 of those numbers? What's the most efficient way to do that? Of course once again i dont want to calculate $AB+AC+AD+...+DE + ABCD + ABCE + ... + BCDE$. Please note that in my real case i would have something around 30 possible numbers and i could need the sum of the products of, say, 5, 12, 18,19 or 23 of them. I know the formula $(1+Ax)(1+Bx)(1+Cx)(1+Dx)(1+Ex)$ would give me the answer by just taking the coefficients of the terms of 2nd and 4th grade but this solution requires me first to calculate everything (that is, a long polynomial) while i would prefer a closed general form. For instance, if i do really have 26 numbers and i need the sum of the products of only 20 of them i don't want to calculate first $(1+Ax)(1+Bx)...(1+Zx)$, if possible.