Sum of products of n-tuples Let's say I have an array of numbers {a,b,c,d,e} and want to calculate the sum of product of all triples abc+abd+...+cde.
I can calculate it very fast without generating all triples using this formula
F(n,k)= k*F(n-1, k-1)+ F(n-1, k) with two loops

       int[] values={a, b, c, d, e...}; 
       int k = 3;
       int[,] F = new int[values.Count, k];
       ...
        for(int i = 0; i &lt; values.Count; i++)       
            for(int j = 0; j &lt; k &amp;&amp; j &lt;= i; j++)
                F[i, j] = values[i] * F[i - 1, j - 1] + F[i - 1, j];


Now I have this array of groups {{a1,a2,a3..an}, {b1,b2,b3 ...bn}, {c1,c2...} } and every element of a triple must be in different group.
a1*b2*c1 is a valid triple but a1*a2*b1 is not allowed because a1, a2 are in the same group. It's possible to generalize the above algorithm to find the sum of valid triples (quadruple or n-tuple)?
We have the following identity:

$$\sum_{i,j,k} a_i b_j c_k = (a_1+\dots+a_n) \times (b_1+\dots+b_n) \times (c_1 + \dots + c_n).$$

Therefore, one can compute the sum of all valid triples in $O(n)$ time by first computing the sum of the $a_i'$, the sum of the $b_i$'s, the sum of the $c_i$'s, and then multiplying these three sums.  This generalizes: you can find the sum of valid k-tuples in $O(kn)$ time.