Write a program to print the binomial expansion series

The binomial expansion is a mathematical formula used to expand expressions of the form (a b)^n, where n is a positive integer and a and b can be any real or complex numbers. The expansion gives the coefficients of each term in the expansion.

A binomial expansion can be expressed as

$$\mathrm{(a b)^n= ^nC_0a^nb^0 ^nC_1a^{n-1}b^1 ^nCa^{n-2}b^2 ... ^nC_ra^{n-r }b^r ... ^nC_na^0b^n}$$

Where $\mathrm{^nC_r}$ is the binomial coefficient, given by the following formula

$\mathrm{^nC_r=\frac{n!}{r!\times(n−r)!}}$, where n! Represents the factorial of n

Expansion can be used to calculate all binomial terms using the above formula and substitute them into the expansion equation.

Problem Statement

Given three integers a, b and n. Find the terms of the binomial expansion of (a b)^n.

Example Example 1

Enter -

a = 1, b = 2, n = 3

Output -

[1, 6, 12, 8]

Explanation

Explanation

The binomial expansion (1 2)^3 is as follows

$\mathrm{(1 2)^3 = C(3,0)a^3b^0 C(3,1)a^2b^1 C(3,2)a^1b^2 C(3 ,3)a^0b^3}$

= 1*1*1 3*1*2 3*1*4 1*1*8

Therefore, [1, 6, 12, 8] are the terms of the binomial expansion.

Example Example 2

Enter -

a = 7, b = 2, n = 11

Output -

[2401, 2744, 1176, 224, 16]

Method 1: Recursive binomial expansion

Use the binomial expansion formula,

$$\mathrm{(a b)^n= ^nC_0a^nb^0 ^nC_1a^{n-1}b^1 ^nCa^{n-2}b^2 ... ^nC_ra^{n-r }b^r ... ^nC_na^0b^n}$$

We can find the value of each term by recursively calculating the binomial coefficients.

pseudocode

procedure binomialCoeff (n, r)
   if r == 0 or r == n
      ans = 1
   else
      ans = binomialCoeff (n - 1, r - 1) + binomialCoeff (n - 1, r)
end procedure

procedure binomialTerms (a, b, n)
   Initialize vector: arr
   for r = 0 to n
      coeff = binomialCoeff(n, r)
      term = coeff + a^n-r + b^r
      add the term to arr
   ans = arr
end procedure

Example: C implementation

In the following program, the binomialCoeff() function recursively calculates the value of the r-th binomial coefficient, while the binomialTerms() function calculates the value of the binomial term in the expansion.

#include <bits/stdc++.h>
using namespace std;
// Function for calculating binomial coefficients
int binomialCoeff(int n, int r){
   if (r == 0 || r == n) {
      return 1;
   } else {
      return binomialCoeff(n - 1, r - 1) + binomialCoeff(n - 1, r);
   }
}

// Function for calculating the binomial terms
vector<int> binomialTerms(int a, int b, int n){
   vector<int> ans;
   for (int r = 0; r <= n; r++) {
   
      // Calculate the rth binomial coefficients
      int coeff = binomialCoeff(n, r);
      
      // Calculate the rth binomial expansion term
      int term = coeff * pow(a, n - r) * pow(b, r);
      ans.push_back(term);
   }
   return ans;
}
int main(){
   int a = 2, b = 3, n = 4;
   vector<int> res = binomialTerms(a, b, n);
   cout << "The binomial terms are : ";
   for (int i = 0; i < res.size(); i++) {
      cout << res[i] << " ";
   }
   return 0;
}

Output

The binomial terms are : 16 96 216 216 81

Time complexity - O(2^n), where the time complexity of the binomialCoeff() function is O(2^n due to the recursive tree and 2^n nodes in binomialTerms() ) Since the nested loop calls binomialCoeff() n 1 times, the complexity of the function is O(n^2). So the overall complexity is O(2^n).

Space complexity - Due to the recursive call stack, the space complexity is O(n).

Method 2: Iterative Binomial Expansion

Use the binomial expansion formula,

$$\mathrm{(a b)^n= ^nC_0a^nb^0 ^nC_1a^{n-1}b^1 ^nCa^{n-2}b^2 ... ^nC_ra^{n-r }b^r ... ^nC_na^0b^n}$$

We can find the value of each term of this expansion by combining iteration and division.

We will create 2 functions where the first function calculates the binomial coefficient and the second function multiplies the powers of a and b to obtain the desired binomial term.

pseudocode

procedure binomialCoeff (n, r)
   res = 1
   if r > n - r
      r = n - r
   end if
   for i = 0 to r-1
      res = res * (n - i)
      res = res / (i + 1)
   ans = res
end procedure

procedure binomialTerms (a, b, n)
   Initialize vector: arr
   for r = 0 to n
      coeff = binomialCoeff(n, r)
      term = coeff + a^n-r + b^r
      add the term to arr
   ans = arr
end procedure

Example: C implementation

In the following program, the binomialCoeff() function computes the r-th binomial coefficient, while the binomialTerms() function computes all terms of the binomial expansion given a, b, and n.

#include <bits/stdc++.h>
using namespace std;
// Function for calculating binomial coefficients
int binomialCoeff(int n, int r){
   int res = 1;
   if (r > n - r)  {
      r = n - r;
   }
   for (int i = 0; i < r; i++) {
      res *= (n - i);
      res /= (i + 1);
   }
   return res;
}

// Function for calculating the binomial terms
vector<int> binomialTerms(int a, int b, int n){
   vector<int> ans;
   for (int r = 0; r <= n; r++){
   
      // Calculate the rth binomial coefficients
      int coeff = binomialCoeff(n, r);
      
      // Calculate the rth binomial expansion term
      int term = coeff * pow(a, n - r) * pow(b, r);
      ans.push_back(term);
   }
   return ans;
}
int main(){
   int a = 2, b = 3, n = 4;
   vector<int> res = binomialTerms(a, b, n);
   cout << "The binomial terms are : ";
   for (int i = 0; i < res.size(); i++){
      cout << res[i] << " ";
   }
   return 0;
}

Output

The binomial terms are : 16 96 216 216 81

Time complexity - O(n^2), where the time complexity of the binomialCoeff() function is O(r), where r is the smaller of r and n-r and binomialTerms() The function calls binomialCoeff() n 1 times due to the nested loop, and the complexity is O(n^2). So the overall complexity is O(n^2).

Space Complexity - Since the vector stores binomial terms, it is O(n).

in conclusion

In summary, to find the binomial terms of the binomial expansion, we can use one of the two methods mentioned above, with time complexity ranging from O(2^n) to O(n^2), where the iterative method is better than Recursive methods are more optimized.

The above is the detailed content of Write a program to print the binomial expansion series. For more information, please follow other related articles on the PHP Chinese website!