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: 540
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:

SectKace
Posts: 1
Joined: Tue Jun 04, 2019 9:42 am

Re: Sum of products of n-tuples

Post by SectKace » Tue Jun 04, 2019 9:54 am

albert_nik wrote:
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)?
Like it was said, if you wish to modify the code there is a very simple solution. Obviously do not multiple the variables in combinations, rather multiply the value by the count in the set of that variable. Then find the overall product, once performing this simple procedure. Should really take 2 lines of code, in a method with few inputs.

Post Reply