Given a positive integer n. The task is to find the sum of product of consecutive binomial coefficient i.e
nC0*nC1 + nC1*nC2 + ….. + nCn-1*nCn
Examples:
Input : n = 3
Output : 15
3C0*3C1 + 3C1*3C2 +3C2*3C3
= 1*3 + 3*3 + 3*1
= 3 + 9 + 3
= 15
Input : n = 4
Output : 56
Method 1: The idea is to find all the binomial coefficients up to nth term and find the sum of the product of consecutive coefficients.
Below is the implementation of this approach:
C++
// CPP Program to find sum of product of// consecutive Binomial Coefficient.#include <bits/stdc++.h>using namespace std;#define MAX 100// Find the binomial coefficient upto nth termvoid binomialCoeff(int C[], int n){ C[0] = 1; // nC0 is 1 for (int i = 1; i <= n; i++) { // Compute next row of pascal triangle using // the previous row for (int j = min(i, n); j > 0; j--) C[j] = C[j] + C[j - 1]; }}// Return the sum of the product of// consecutive binomial coefficient.int sumOfproduct(int n){ int sum = 0; int C[MAX] = { 0 }; binomialCoeff(C, n); // finding the sum of product of // consecutive coefficient. for (int i = 0; i <= n; i++) sum += C[i] * C[i + 1]; return sum;}// Driven Programint main(){ int n = 3; cout << sumOfproduct(n) << endl; return 0;} |
Java
// Java Program to find sum of product of// consecutive Binomial Coefficient.import java.io.*;class GFG { static int MAX = 100;// Find the binomial coefficient upto nth termstatic void binomialCoeff(int C[], int n){ C[0] = 1; // nC0 is 1 for (int i = 1; i <= n; i++) { // Compute next row of pascal triangle using // the previous row for (int j = Math.min(i, n); j > 0; j--) C[j] = C[j] + C[j - 1]; }}// Return the sum of the product of// consecutive binomial coefficient.static int sumOfproduct(int n){ int sum = 0; int C[] = new int[MAX]; binomialCoeff(C, n); // finding the sum of product of // consecutive coefficient. for (int i = 0; i <= n; i++) sum += C[i] * C[i + 1]; return sum;}// Driven Program public static void main (String[] args) { int n = 3; System.out.println( sumOfproduct(n)); }} // This code is contributed by inder_verma.. |
Python3
# Python3 Program to find sum of product # of consecutive Binomial Coefficient.MAX = 100;# Find the binomial coefficient upto # nth termdef binomialCoeff(C, n): C[0] = 1; # nC0 is 1 for i in range(1, n + 1): # Compute next row of # pascal triangle using # the previous row for j in range(min(i, n), 0, -1): C[j] = C[j] + C[j - 1]; return C;# Return the sum of the product of # consecutive binomial coefficient.def sumOfproduct(n): sum = 0; C = [0] * MAX; C = binomialCoeff(C, n); # finding the sum of # product of consecutive # coefficient. for i in range(n + 1): sum += C[i] * C[i + 1]; return sum;# Driver Coden = 3;print(sumOfproduct(n));# This code is contributed by mits |
C#
// C# Program to find sum of // product of consecutive// Binomial Coefficient.using System;class GFG {static int MAX = 100;// Find the binomial coefficient// upto nth termstatic void binomialCoeff(int []C, int n){ C[0] = 1; // nC0 is 1 for (int i = 1; i <= n; i++) { // Compute next row of pascal // triangle using the previous row for (int j = Math.Min(i, n); j > 0; j--) C[j] = C[j] + C[j - 1]; }}// Return the sum of the product of// consecutive binomial coefficient.static int sumOfproduct(int n){ int sum = 0; int []C = new int[MAX]; binomialCoeff(C, n); // finding the sum of product of // consecutive coefficient. for (int i = 0; i <= n; i++) sum += C[i] * C[i + 1]; return sum;}// Driven Codepublic static void Main (){ int n = 3; Console.WriteLine(sumOfproduct(n));}}// This code is contributed by anuj_67 |
Javascript
<script>// Javascript Program to find sum of product of// consecutive Binomial Coefficient.var MAX = 100;// Find the binomial coefficient upto nth termfunction binomialCoeff(C, n){ C[0] = 1; // nC0 is 1 for (var i = 1; i <= n; i++) { // Compute next row of pascal triangle using // the previous row for (var j = Math.min(i, n); j > 0; j--) C[j] = C[j] + C[j - 1]; }}// Return the sum of the product of// consecutive binomial coefficient.function sumOfproduct(n){ var sum = 0; var C = Array(MAX).fill(0); binomialCoeff(C, n); // finding the sum of product of // consecutive coefficient. for (var i = 0; i <= n; i++) sum += C[i] * C[i + 1]; return sum;}// Driven Programvar n = 3;document.write( sumOfproduct(n));</script> |
PHP
<?php// PHP Program to find sum // of product of consecutive// Binomial Coefficient.$MAX = 100;// Find the binomial// coefficient upto // nth termfunction binomialCoeff($C, $n){ $C[0] = 1; // nC0 is 1 for ($i = 1; $i <= $n; $i++) { // Compute next row of // pascal triangle using // the previous row for ($j = min($i, $n); $j > 0; $j--) $C[$j] = $C[$j] + $C[$j - 1]; } return $C;}// Return the sum of the // product of consecutive // binomial coefficient.function sumOfproduct($n){ global $MAX; $sum = 0; $C = array_fill(0, $MAX, 0); $C = binomialCoeff($C, $n); // finding the sum of // product of consecutive // coefficient. for ($i = 0; $i <= $n; $i++) $sum += $C[$i] * $C[$i + 1]; return $sum;}// Driver Code$n = 3;echo sumOfproduct($n);// This code is contributed by mits?> |
Output
15
Method 2:
We know,
(1 + x)n = nC0 + nC1*x + nC2*x2 + …. + nCn*xn … (1)
(1 + 1/x)n = nC0 + nC1/x + nC2/x2 + …. + nCn/xn … (2)
Multiplying (1) and (2), we get
(1 + x)2n/xn = (nC0 + nC1*x + nC2*x2 + …. + nCn*xn) * (nC0 + nC1/x + nC2/x2 + …. + nCn/xn)
(2nC0 + 2nC1*x + 2nC2*x2 + …. + 2nCn*xn)/xn = (nC0 + nC1*x + nC2*x2 + …. + nCn*xn) * (nC0 + nC1/x + nC2/x2 + …. + nCn/xn)
Now, find the coefficient of x in LHS,
Observe rth term of expansion in numerator is 2nCrxr.
To find the coefficient of x in (1 + x)2n/xn, r should be n + 1, because power of x in denominator will reduce it.
So, coefficient of x in LHS = 2nCn + 1 or 2nCn – 1
Now, find the coefficient of x in RHS,
r th term of first expansion of multiplication is nCr * xr
t th term of second expansion of multiplication is nCt / xt
So term after multiply will be nCr * xr * nCt / xt or
nCr * nCt * xr / xt
Put r = t + 1, we get,
nCt+1 * nCt * x
Observe there will be n such term in the expansion of multiply, so t range from 0 to n – 1.
Therefore, coefficient of x in RHS = nC0*nC1 + nC1*nC2 + ….. + nCn-1*nCn
Comparing coefficient of x in LHS and RHS, we can say,
nC0*nC1 + nC1*nC2 + ….. + nCn-1*nCn = 2nCn – 1
Below is implementation of this approach:
C++
// CPP Program to find sum of product of // consecutive Binomial Coefficient.#include <bits/stdc++.h>using namespace std;#define MAX 100// Find the binomial coefficient up to nth // termint binomialCoeff(int n, int k){ int C[k + 1]; memset(C, 0, sizeof(C)); C[0] = 1; // nC0 is 1 for (int i = 1; i <= n; i++) { // Compute next row of pascal triangle // using the previous row for (int j = min(i, k); j > 0; j--) C[j] = C[j] + C[j - 1]; } return C[k];}// Return the sum of the product of// consecutive binomial coefficient.int sumOfproduct(int n){ return binomialCoeff(2 * n, n - 1);}// Driven Programint main(){ int n = 3; cout << sumOfproduct(n) << endl; return 0;} |
Java
// Java Program to find sum of // product of consecutive // Binomial Coefficient.import java.io.*;class GFG { static int MAX = 100; // Find the binomial coefficient // up to nth term static int binomialCoeff(int n, int k) { int C[] = new int[k + 1]; // memset(C, 0, sizeof(C)); C[0] = 1; // nC0 is 1 for (int i = 1; i <= n; i++) { // Compute next row of // pascal triangle // using the previous row for (int j = Math.min(i, k); j > 0; j--) C[j] = C[j] + C[j - 1]; } return C[k];}// Return the sum of the // product of consecutive// binomial coefficient.static int sumOfproduct(int n){ return binomialCoeff(2 * n, n - 1);}// Driver Codepublic static void main (String[] args) { int n = 3; System.out.println(sumOfproduct(n));}}// This code is contributed// by shiv_bhakt. |
Python3
# Python3 Program to find sum of product # of consecutive Binomial Coefficient.MAX = 100;# Find the binomial coefficient # up to nth termdef binomialCoeff(n, k): C = [0] * (k + 1); C[0] = 1; # nC0 is 1 for i in range(1, n + 1): # Compute next row of pascal triangle # using the previous row for j in range(min(i, k), 0, -1): C[j] = C[j] + C[j - 1]; return C[k];# Return the sum of the product of# consecutive binomial coefficient.def sumOfproduct(n): return binomialCoeff(2 * n, n - 1);# Driver Coden = 3;print(sumOfproduct(n));# This code is contributed by mits |
C#
// C# Program to find sum of // product of consecutive // Binomial Coefficient.using System;class GFG{ // Find the binomial // coefficient up to // nth term static int binomialCoeff(int n, int k) { int []C = new int[k + 1]; // memset(C, 0, sizeof(C)); C[0] = 1; // nC0 is 1 for (int i = 1; i <= n; i++) { // Compute next row of // pascal triangle // using the previous row for (int j = Math.Min(i, k); j > 0; j--) C[j] = C[j] + C[j - 1]; } return C[k];}// Return the sum of the // product of consecutive// binomial coefficient.static int sumOfproduct(int n){ return binomialCoeff(2 * n, n - 1);}// Driver Codestatic public void Main (){ int n = 3; Console.WriteLine(sumOfproduct(n));}}// This code is contributed// by @ajit. |
Javascript
<script> // Javascript Program to find sum of // product of consecutive // Binomial Coefficient. let MAX = 100; // Find the binomial coefficient // up to nth term function binomialCoeff(n, k) { let C = new Array(k + 1); C.fill(0); // memset(C, 0, sizeof(C)); C[0] = 1; // nC0 is 1 for (let i = 1; i <= n; i++) { // Compute next row of // pascal triangle // using the previous row for (let j = Math.min(i, k); j > 0; j--) C[j] = C[j] + C[j - 1]; } return C[k]; } // Return the sum of the // product of consecutive // binomial coefficient. function sumOfproduct(n) { return binomialCoeff(2 * n, n - 1); } let n = 3; document.write(sumOfproduct(n));// This code is contributed by suresh07.</script> |
PHP
<?php// PHP Program to find sum of product of // consecutive Binomial Coefficient.$MAX = 100;// Find the binomial coefficient // up to nth termfunction binomialCoeff($n, $k){ $C = array_fill(0, ($k + 1), 0); $C[0] = 1; // nC0 is 1 for ($i = 1; $i <= $n; $i++) { // Compute next row of pascal triangle // using the previous row for ($j = min($i, $k); $j > 0; $j--) $C[$j] = $C[$j] + $C[$j - 1]; } return $C[$k];}// Return the sum of the product of// consecutive binomial coefficient.function sumOfproduct($n){ return binomialCoeff(2 * $n, $n - 1);}// Driver Code$n = 3;echo sumOfproduct($n);// This code is contributed by mits?> |
Output:
15
Time Complexity: O(n*k)
Auxiliary Space: O(k)
Efficient approach : space optimization
In this approach we use variables instead of array of size K to solve the problems by calculating Binomial Coefficient using iterative approach.
Implementations Steps:
- Define the binomialCoeff function to calculate the binomial coefficient using an iterative approach.
- Initialize a variable res to 1.
- Optimize the calculation by choosing the smaller value of k if k is greater than n – k.
- Use a loop to calculate the binomial coefficient by multiplying n – i and dividing by i + 1.
- Return the calculated binomial coefficient.
- Define the sumOfproduct function to calculate the sum of the product of consecutive binomial coefficients.
- Call the binomialCoeff function with arguments 2 * n and n – 1 to calculate the binomial coefficient.
- Return the calculated binomial coefficient.
Implementation:
C++
#include <iostream>using namespace std;// Function to calculate the binomial coefficientint binomialCoeff(int n, int k){ int res = 1; // Optimize calculation by choosing the smaller value of k if (k > n - k) k = n - k; // Calculate binomial coefficient using iterative approach for (int i = 0; i < k; i++) { res *= (n - i); res /= (i + 1); } return res;}// Function to calculate the sum of product of consecutive binomial coefficientsint sumOfproduct(int n){ // Calculate the binomial coefficient for 2n choose n-1 return binomialCoeff(2 * n, n - 1);}// Driven programint main(){ int n = 3; // Function call cout << sumOfproduct(n) << endl; return 0;} |
Python3
# Function to calculate the binomial coefficientdef binomial_coeff(n, k): res = 1 # Optimize calculation by choosing the smaller value of k if k > n - k: k = n - k # Calculate binomial coefficient using an iterative approach for i in range(k): res *= (n - i) res //= (i + 1) return res# Function to calculate the sum of the product of consecutive binomial coefficientsdef sum_of_product(n): # Calculate the binomial coefficient for 2n choose n-1 return binomial_coeff(2 * n, n - 1)# Driven Codeif __name__ == "__main__": n = 3 # Function call print(sum_of_product(n)) |
C#
using System;class Program{ // Function to calculate the binomial coefficient static int BinomialCoeff(int n, int k) { int res = 1; // Optimize calculation by choosing the smaller value of k if (k > n - k) k = n - k; // Calculate binomial coefficient using iterative approach for (int i = 0; i < k; i++) { res *= (n - i); res /= (i + 1); } return res; } // Function to calculate the sum of product of consecutive binomial coefficients static int SumOfProduct(int n) { // Calculate the binomial coefficient for 2n choose n-1 return BinomialCoeff(2 * n, n - 1); } // Driver code static void Main(string[] args) { int n = 3; // Function call Console.WriteLine(SumOfProduct(n)); }} |
Output:
15
Time Complexity: O(k)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
