The sum of the products of all combinations taken from 1 to n

If you take the numbers one by one from 1 to n, there may be many combinations.

For example, if we take only one number at a time, the number of combinations will be nC1.

If we take two numbers at a time, the number of combinations will be nC2. Hence, the total number of combinations will be nC1 nC2 … nCn.

To find the sum of all combinations, we must use an efficient method. Otherwise, the time and space complexity will become very high.

Problem Statement

Find the sum of the products of all combinations of numbers taken each time from 1 to N.

N is a given number.

Example

enter

N = 4

Output

f(1) = 10
f(2) = 35
f(3) = 50
f(4) = 24

Explanation

f(x) is the sum of the product of all combinations taken x at a time.
f(1) = 1 + 2+ 3+ 4 = 10
f(2) = (1*2) + (1*3) + (1*4) + (2*3) + (2*4) + (3*4) = 35
f(3) = (1*2*3) + (1*2*4) +(1*3*4) + (2*3*4) = 50
f(4) = (1*2*3*4) = 24 

enter

N = 5

Output

f(1) = 15
f(2) = 85
f(3) = 225
f(4) = 274
f(5) = 120

Brute Force Approach

The brute force method is to generate all combinations recursively, find their products, and then find the corresponding sum.

Recursive C program example

The following is a recursive C program that is used to find the sum of the products taken each time in all combinations (from 1 to N)

#include <bits/stdc++.h>
using namespace std;
//sum of each combination
int sum = 0;
void create_combination(vector<int>vec, vector<int>combinations, int n, int r, int depth, int index) {
   // if we have reached sufficient depth
   if (index == r) {
      //find the product of the combination
    	int prod = 1;
    	for (int i = 0; i < r; i++)
    	prod = prod * combinations[i];
    	// add the product to sum
    	sum += prod;
    	return;
   }
   // recursion to produce a different combination
   for (int i = depth; i < n; i++) {
      combinations[index] = vec[i];
   	  create_combination(vec, combinations, n, r, i + 1, index + 1);
   }
}
//Function to print the sum of products of
//all combinations taken 1-N at a time
void get_combinations(vector<int>vec, int n) {
   for (int i = 1; i <= n; i++) {
      // vector for storing combination
         //int *combi = new int[i];
    	vector<int>combinations(i);
    	// call combination with r = i
    	// combination by taking i at a time
    	create_combination(vec, combinations, n, i, 0, 0);
    	// displaying sum of the product of combinations
    	cout << "f(" << i << ") = " << sum << endl;
        sum = 0;
    }
}
int main() {
   int n = 5;
   //creating vector of size n
   vector<int>vec(n);
   // storing numbers from 1-N in the vector
   for (int i = 0; i < n; i++)
   	vec[i] = i + 1;
   //Function call
   get_combinations(vec, n);
   return 0;
}

Output

f(1) = 15
f(2) = 85
f(3) = 225
f(4) = 274
f(5) = 120

By creating the recursion tree of this approach, it is visible that the time complexity is exponential. Also, many steps get repeated which makes the program redundant. Hence, it is highly inefficient.

Efficient Approach (Dynamic Programming)

An effective solution would be to use dynamic programming and remove the redundancies.

Dynamic programming is a technique in which a problem is divided into subproblems. The subproblems are solved, and their results are saved to avoid repetitions.

Example C Program using Dynamic Programming

Below is a C Program using Dynamic Programming to find the sum of all combinations taken (1 to N) at a time .

#include <bits/stdc++.h>
using namespace std;
//Function to find the postfix sum array
void postfix(int a[], int n) {
for (int i = n - 1; i > 0; i--)
   a[i - 1] = a[i - 1] + a[i];
}
//Function to store the previous results, so that the computations don't get repeated
void modify(int a[], int n) {
   for (int i = 1; i < n; i++)
      a[i - 1] = i * a[i];
}
//Function to find the sum of all combinations taken 1 to N at a time
void get_combinations(int a[], int n) {
   int sum = 0;
   // sum of combinations taken 1 at a time is simply the sum of the numbers 
   // from 1 - N
   for (int i = 1; i <= n; i++)
   	  sum += i;
   cout << "f(1) = " << sum <<endl;
      // Finding the sum of products for all combination
   for (int i = 1; i < n; i++) {
   	  //Function call to find the postfix array
   	  postfix(a, n - i + 1);
      // sum of products taken i+1 at a time
   	  sum = 0;
      for (int j = 1; j <= n - i; j++) {
         sum += (j * a[j]);
      }
      cout << "f(" << i + 1 << ") = " << sum <<endl;
      //Function call to modify the array for overlapping problem
      modify(a, n);
   }
}
int main() {
   int n = 5;
  int *a = new int[n];
   // storing numbers from 1 to N
   for (int i = 0; i < n; i++)
	  a[i] = i + 1;
   //Function call
   get_combinations(a, n);
   return 0;
}

Output

f(1) = 15
f(2) = 85
f(3) = 225
f(4) = 274
f(5) = 120

in conclusion

In this article, we discussed the problem of finding the sum of the products of all combinations from 1 to N.

We started with a brute force approach with exponential time complexity and then modified it using dynamic programming. C programs for both methods are also provided.

The above is the detailed content of The sum of the products of all combinations taken from 1 to n. For more information, please follow other related articles on the PHP Chinese website!