Sum of products of n-tuples

Arrangements, combinations and permutations, probability, ...
Post Reply
albert_nik
Posts: 18
Joined: Wed Apr 22, 2009 10:46 am

Sum of products of n-tuples

Post by albert_nik » Thu Oct 01, 2015 8:53 am

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)= v[k]*F(n-1, k-1)+ F(n-1, k) with two loops

Code: Select all

       int[] values={a, b, c, d, e...}; 
       int k = 3;
       int[,] F = new int[values.Count, k];
       ...
        for(int i = 0; i < values.Count; i++)       
            for(int j = 0; j < k && j <= 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 (quadruples or n-tuples)?

User avatar
jaap
Posts: 533
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

Re: Sum of products of n-tuples

Post by jaap » Thu Oct 01, 2015 12:36 pm

Isn't it just this?
Expand
(a1+a2+a3+..+an)*(b1+b2+...+bn)*(c1+c2+...+cn)

albert_nik
Posts: 18
Joined: Wed Apr 22, 2009 10:46 am

Re: Sum of products of n-tuples

Post by albert_nik » Thu Oct 01, 2015 12:48 pm

jaap wrote:Isn't it just this?
Expand
(a1+a2+a3+..+an)*(b1+b2+...+bn)*(c1+c2+...+cn)
Expand
I feel so stupid :oops:

Post Reply