## Sum of products of n-tuples

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

### 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)= 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)?

jaap
Posts: 540
Joined: Tue Mar 25, 2008 3:57 pm
Contact:

### Re: Sum of products of n-tuples

Isn't it just this?
Expand

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

### Re: Sum of products of n-tuples

jaap wrote:Isn't it just this?
Expand
Expand

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

### Re: Sum of products of n-tuples

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.