Sum of product of consecutive Binomial Coefficients

0 0 11 minutes read

Given a positive integer n. The task is to find the sum of product of consecutive binomial coefficient i.e
ⁿC₀*ⁿC₁ + ⁿC₁*ⁿC₂ + ….. + ⁿC_n-1*ⁿC_n

Examples:

Input : n = 3
Output : 15
³C₀*³C₁ + ³C₁*³C₂ +³C₂*³C₃
= 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 term
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 = 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 Program
int 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 term
static 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 term
def 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 Code
n = 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 term
static 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 Code
public 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 term
function 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 Program
var 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 term
function 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

Method 2:
We know,
(1 + x)ⁿ = ⁿC₀ + ⁿC₁*x + ⁿC₂*x² + …. + ⁿC_n*xⁿ … (1)
(1 + 1/x)ⁿ = ⁿC₀ + ⁿC₁/x + ⁿC₂/x² + …. + ⁿC_n/xⁿ … (2)
Multiplying (1) and (2), we get
(1 + x)²ⁿ/xⁿ = (ⁿC₀ + ⁿC₁*x + ⁿC₂*x² + …. + ⁿC_n*xⁿ) * (ⁿC₀ + ⁿC₁/x + ⁿC₂/x² + …. + ⁿC_n/xⁿ)
(²ⁿC₀ + ²ⁿC₁*x + ²ⁿC₂*x² + …. + ²ⁿC_n*xⁿ)/xⁿ = (ⁿC₀ + ⁿC₁*x + ⁿC₂*x² + …. + ⁿC_n*xⁿ) * (ⁿC₀ + ⁿC₁/x + ⁿC₂/x² + …. + ⁿC_n/xⁿ)
Now, find the coefficient of x in LHS,
Observe rth term of expansion in numerator is ²ⁿC_rx^r.
To find the coefficient of x in (1 + x)²ⁿ/xⁿ, r should be n + 1, because power of x in denominator will reduce it.
So, coefficient of x in LHS = ²ⁿC_{n + 1} or ²ⁿC_{n – 1}
Now, find the coefficient of x in RHS,
r th term of first expansion of multiplication is ⁿC_r * x^r
t th term of second expansion of multiplication is ⁿC_t / x^t
So term after multiply will be ⁿC_r * x^r * ⁿC_t / x^t or
ⁿC_r * ⁿC_t * x^r / x^t
Put r = t + 1, we get,
ⁿC_t+1 * ⁿC_t * 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 = ⁿC₀*ⁿC₁ + ⁿC₁*ⁿC₂ + ….. + ⁿC_n-1*ⁿC_n
Comparing coefficient of x in LHS and RHS, we can say,
ⁿC₀*ⁿC₁ + ⁿC₁*ⁿC₂ + ….. + ⁿC_n-1*ⁿC_n = ²ⁿC_{n – 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 
// term
int 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 Program
int 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 Code
public 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 term
def 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 Code
n = 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 Code
static 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 term
function 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:

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 coefficient
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
int sumOfproduct(int n)
{
    // Calculate the binomial coefficient for 2n choose n-1
    return binomialCoeff(2 * n, n - 1);
}
 
// Driven program
int main()
{
    int n = 3;
     
    // Function call
    cout << sumOfproduct(n) << endl;
    return 0;
}

Python3

# Function to calculate the binomial coefficient
def 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 coefficients
def sum_of_product(n):
    # Calculate the binomial coefficient for 2n choose n-1
    return binomial_coeff(2 * n, n - 1)
 
# Driven Code
if __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:

Time Complexity: O(k)

Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!