Maximum binomial coefficient term value

0 0 9 minutes read

Given a positive integer n. The task is to find the maximum coefficient term in all binomial coefficient.
The binomial coefficient series is
ⁿC₀, ⁿC₁, ⁿC₂, …., ⁿC_r, …., ⁿC_n-2, ⁿC_n-1, ⁿC_n
the task is to find maximum value of ⁿC_r.

Examples:

Input : n = 4
Output : 6
⁴C₀ = 1
⁴C₁ = 4
⁴C₂ = 6
⁴C₃ = 1
⁴C₄ = 1
So, maximum coefficient value is 6.

Input : n = 3
Output : 3

Method 1: (Brute Force)
The idea is to find all the value of binomial coefficient series and find the maximum value in the series.

Below is the implementation of this approach:

C++

// CPP Program to find maximum binomial coefficient
// term
#include<bits/stdc++.h>
using namespace std;
 
// Return maximum binomial coefficient term value.
int maxcoefficientvalue(int n)
{
    int C[n+1][n+1];
  
    // Calculate value of Binomial Coefficient in 
    // bottom up manner
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= min(i, n); j++)
        {
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
  
            // Calculate value using previously
            // stored values
            else
                C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
         
    // finding the maximum value.
    int maxvalue = 0;
    for (int i = 0; i <= n; i++)
        maxvalue = max(maxvalue, C[n][i]);
         
    return maxvalue;
}
 
// Driven Program
int main()
{
    int n = 4;
    cout << maxcoefficientvalue(n) << endl;
    return 0;
} 

Java

// Java Program to find
// maximum binomial 
// coefficient term
import java.io.*;
 
class GFG 
{
// Return maximum binomial 
// coefficient term value.
static int maxcoefficientvalue(int n)
{
    int [][]C = new int[n + 1][n + 1];
 
    // Calculate value of 
    // Binomial Coefficient  
    // in bottom up manner
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; 
                 j <= Math.min(i, n); j++)
        {
             
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
 
            // Calculate value
            // using previously
            // stored values
            else
                C[i][j] = C[i - 1][j - 1] + 
                          C[i - 1][j];
        }
    }
         
    // finding the
    // maximum value.
    int maxvalue = 0;
     
    for (int i = 0; i <= n; i++)
        maxvalue = Math.max(maxvalue, C[n][i]);
         
    return maxvalue;
}
 
// Driver Code
public static void main (String[] args) 
{
    int n = 4;
    System.out.println(maxcoefficientvalue(n));
}
}
 
// This code is contributed by ajit

Python3

# Python3 Program to find 
# maximum binomial 
# coefficient term
 
# Return maximum binomial 
# coefficient term value.
def maxcoefficientvalue(n):
    C = [[0 for x in range(n + 1)]
            for y in range(n + 1)];
             
    # Calculate value of
    # Binomial Coefficient in
    # bottom up manner
    for i in range(n + 1):
        for j in range(min(i, n) + 1):
             
            # Base Cases
            if (j == 0 or j == i):
                C[i][j] = 1;
                 
            # Calculate value
            # using previously
            # stored values
            else:
                C[i][j] = (C[i - 1][j - 1] +
                           C[i - 1][j]);
     
    # finding the maximum value.
    maxvalue = 0;
    for i in range(n + 1):
        maxvalue = max(maxvalue, C[n][i]);
     
    return maxvalue;
 
# Driver Code
n = 4;
print(maxcoefficientvalue(n));
 
# This code is contributed by mits

C#

// C# Program to find maximum binomial coefficient
// term
using System;
 
public class GFG {
         
    // Return maximum binomial coefficient term value.
    static int maxcoefficientvalue(int n)
    {
        int [,]C = new int[n+1,n+1];
     
        // Calculate value of Binomial Coefficient in 
        // bottom up manner
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= Math.Min(i, n); j++)
            {
                 
                // Base Cases
                if (j == 0 || j == i)
                    C[i,j] = 1;
     
                // Calculate value using previously
                // stored values
                else
                    C[i,j] = C[i-1,j-1] + C[i-1,j];
            }
        }
             
        // finding the maximum value.
        int maxvalue = 0;
         
        for (int i = 0; i <= n; i++)
            maxvalue = Math.Max(maxvalue, C[n,i]);
             
        return maxvalue;
    }
     
    // Driven Program
 
    static public void Main ()
    {
         
        int n = 4;
         
        Console.WriteLine(maxcoefficientvalue(n));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP Program to find 
// maximum binomial 
// coefficient term
 
// Return maximum binomial 
// coefficient term value.
function maxcoefficientvalue($n)
{
 
    // Calculate value of 
    // Binomial Coefficient in 
    // bottom up manner
    for ($i = 0; $i <= $n; $i++)
    {
        for ($j = 0; $j <= min($i, $n); $j++)
        {
             
            // Base Cases
            if ($j == 0 || $j == $i)
                $C[$i][$j] = 1;
 
            // Calculate value
            // using previously
            // stored values
            else
                $C[$i][$j] = $C[$i - 1][$j - 1] + 
                             $C[$i - 1][$j];
        }
    }
         
    // finding the maximum value.
    $maxvalue = 0;
    for ($i = 0; $i <= $n; $i++)
        $maxvalue = max($maxvalue, $C[$n][$i]);
         
    return $maxvalue;
}
 
    // Driver Code
    $n = 4;
    echo maxcoefficientvalue($n), "\n";
 
// This code is contributed by aj_36
?>

Javascript

<script>
 
// JavaScript Program to find 
// maximum binomial 
// coefficient term
               
    // Returns value of 
    // Binomial Coefficient
    // C(n, k)
    function binomialCoeff(n, k)
    {
        let C = new Array(n+1);
         
        // Loop to create 2D array using 1D array
    for (let i = 0; i < C.length; i++) {
        C[i] = new Array(2);
    }
       
        // Calculate value of 
        // Binomial Coefficient 
        // in bottom up manner
        for (let i = 0; i <= n; i++)
        {
            for (let j = 0; 
                j <= Math.min(i, k); j++)
            {
                   
                // Base Cases
                if (j == 0 || j == i)
                    C[i][j] = 1;
       
                // Calculate value using 
                // previously stored values
                else
                    C[i][j] = C[i - 1][j - 1] + 
                              C[i - 1][j];
            }
        }
        return C[n][k];
    }
       
    // Return maximum 
    // binomial coefficient
    // term value.
    function maxcoefficientvalue(n)
    {
           
        // if n is even
        if (n % 2 == 0)
            return binomialCoeff(n, n / 2);
               
        // if n is odd
        else
            return binomialCoeff(n, (n + 1) / 2);
    }
 
// Driver Code
        let n = 4;   
        document.write(maxcoefficientvalue(n));
   
  // This code is contributed by avijitmondal1998..
</script>

Output:

Method 2: (Using formula)

Proof,

Expansion of (x + y)ⁿ are:
ⁿC₀ xⁿ y⁰, ⁿC₁ x^n-1 y¹, ⁿC₂ x^n-2 y², …., ⁿC_r x^n-r y^r, …., ⁿC_n-2 x² y^n-2, ⁿC_n-1 x¹ y^n-1, ⁿC_n x⁰ yⁿ
So, putting x = 1 and y = 1, we get binomial coefficient,
ⁿC₀, ⁿC₁, ⁿC₂, …., ⁿC_r, …., ⁿC_n-2, ⁿC_n-1, ⁿC_n
Let term t_i+1 contains the greatest value in (x + y)ⁿ. Therefore,
t_r+1 >= t_r
ⁿC_r x^n-r y^r >= ⁿC_r-1 x^n-r+1 y^r-1
Putting x = 1 and y = 1,
ⁿC_r >= ⁿC_r-1
ⁿC_r/ⁿC_r-1 >= 1
(using ⁿC_r/ⁿC_r-1 = (n-r+1)/r)
(n-r+1)/r >= 1
(n+1)/r – 1 >= 1
(n+1)/r >= 2
(n+1)/2 >= r
Therefore, r should be less than equal to (n+1)/2.
And r should be integer. So, we get maximum coefficient for r equals to:
(1) n/2, when n is even.
(2) (n+1)/2 or (n-1)/2, when n is odd.

C++

// CPP Program to find maximum binomial coefficient term
#include<bits/stdc++.h>
using namespace std;
 
// Returns value of Binomial Coefficient C(n, k)
int binomialCoeff(int n, int k)
{
    int C[n+1][k+1];
  
    // Calculate value of Binomial Coefficient 
    // in bottom up manner
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= min(i, k); j++)
        {
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
  
            // Calculate value using previously
            // stored values
            else
                C[i][j] = C[i-1][j-1] + C[i-1][j];
        }
    }
  
    return C[n][k];
}
 
// Return maximum binomial coefficient term value.
int maxcoefficientvalue(int n)
{
    // if n is even
    if (n%2 == 0)
        return binomialCoeff(n, n/2);
         
    // if n is odd
    else
        return binomialCoeff(n, (n+1)/2);
}
 
// Driven Program
int main()
{
    int n = 4;
    cout << maxcoefficientvalue(n) << endl;
    return 0;
} 

Java

// Java Program to find 
// maximum binomial 
// coefficient term
import java.io.*;
 
class GFG 
{
             
    // Returns value of 
    // Binomial Coefficient
    // C(n, k)
    static int binomialCoeff(int n, 
                             int k)
    {
        int [][]C = new int[n + 1][k + 1];
     
        // Calculate value of 
        // Binomial Coefficient 
        // in bottom up manner
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; 
                j <= Math.min(i, k); j++)
            {
                 
                // Base Cases
                if (j == 0 || j == i)
                    C[i][j] = 1;
     
                // Calculate value using 
                // previously stored values
                else
                    C[i][j] = C[i - 1][j - 1] + 
                              C[i - 1][j];
            }
        }
        return C[n][k];
    }
     
    // Return maximum 
    // binomial coefficient
    // term value.
    static int maxcoefficientvalue(int n)
    {
         
        // if n is even
        if (n % 2 == 0)
            return binomialCoeff(n, n / 2);
             
        // if n is odd
        else
            return binomialCoeff(n, (n + 1) / 2);
    }
     
    // Driver Code
    public static void main(String[] args) 
    {
        int n = 4;
     
        System.out.println(maxcoefficientvalue(n));
    }
}
 
// This code is contributed
// by akt_mit

Python3

# Python3 Program to find
# maximum binomial
# coefficient term
# Returns value of 
# Binomial Coefficient C(n, k)
def binomialCoeff(n, k):
 
    C=[[0 for x in range(k+1)] for y in range(n+1)] 
 
    # Calculate value of
    # Binomial Coefficient 
    # in bottom up manner
    for i in range(n+1):
        for j in range(min(i,k)+1):
            # Base Cases
            if (j == 0 or j == i):
                C[i][j] = 1;
 
            # Calculate value
            # using previously
            # stored values
            else:
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
 
    return C[n][k];
 
 
# Return maximum binomial
# coefficient term value.
def maxcoefficientvalue(n):
    # if n is even
    if (n % 2 == 0):
        return binomialCoeff(n, int(n / 2));
         
    # if n is odd
    else:
        return binomialCoeff(n, int((n + 1) / 2));
 
# Driver Code
if __name__=='__main__':
    n = 4;
    print(maxcoefficientvalue(n));
 
# This code is contributed by mits

C#

// C# Program to find maximum binomial 
// coefficient term
using System;
 
public class GFG {
         
    // Returns value of Binomial Coefficient
    // C(n, k)
    static int binomialCoeff(int n, int k)
    {
        int [,]C = new int[n+1,k+1];
     
        // Calculate value of Binomial 
        // Coefficient in bottom up manner
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; 
                  j <= Math.Min(i, k); j++)
            {
                 
                // Base Cases
                if (j == 0 || j == i)
                    C[i,j] = 1;
     
                // Calculate value using 
                // previously stored values
                else
                    C[i,j] = C[i-1,j-1] + 
                                   C[i-1,j];
            }
        }
     
        return C[n,k];
    }
     
    // Return maximum binomial coefficient
    // term value.
    static int maxcoefficientvalue(int n)
    {
         
        // if n is even
        if (n % 2 == 0)
            return binomialCoeff(n, n/2);
             
        // if n is odd
        else
            return binomialCoeff(n, (n + 1) / 2);
    }
     
    // Driven Program
    static public void Main ()
    {
         
        int n = 4;
         
        Console.WriteLine(maxcoefficientvalue(n));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP Program to find
// maximum binomial
// coefficient term
// Returns value of 
// Binomial Coefficient C(n, k)
function binomialCoeff($n, $k)
{
    $C[$n + 1][$k + 1] = array(0);
 
    // Calculate value of
    // Binomial Coefficient 
    // in bottom up manner
    for ($i = 0; $i <= $n; $i++)
    {
        for ($j = 0;
             $j <= min($i, $k); $j++)
        {
            // Base Cases
            if ($j == 0 || $j == $i)
                $C[$i][$j] = 1;
 
            // Calculate value
            // using previously
            // stored values
            else
                $C[$i][$j] = $C[$i - 1][$j - 1] + 
                             $C[$i - 1][$j];
        }
    }
 
    return $C[$n][$k];
}
 
// Return maximum binomial
// coefficient term value.
function maxcoefficientvalue($n)
{
    // if n is even
    if ($n % 2 == 0)
        return binomialCoeff($n, $n / 2);
         
    // if n is odd
    else
        return binomialCoeff($n, 
                            ($n + 1) / 2);
}
 
// Driver Code
$n = 4;
echo maxcoefficientvalue($n), "\n";
 
// This code is contributed by m_kit
?>

Javascript

<script>
 
// Javascript Program to find
// maximum binomial
// coefficient term
 
// Returns value of
// Binomial Coefficient
// C(n, k)
function binomialCoeff(n, k)
{
    let C = new Array(n + 1);
    for(let i = 0; i <= n; i++)
    {
        C[i] = new Array(k + 1);
    }
  
    // Calculate value of
    // Binomial Coefficient
    // in bottom up manner
    for(let i = 0; i <= n; i++)
    {
        for(let j = 0; j <= Math.min(i, k); j++)
        {
              
            // Base Cases
            if (j == 0 || j == i)
                C[i][j] = 1;
  
            // Calculate value using
            // previously stored values
            else
                C[i][j] = C[i - 1][j - 1] +
                          C[i - 1][j];
        }
    }
    return C[n][k];
}
  
// Return maximum
// binomial coefficient
// term value.
function maxcoefficientvalue(n)
{
      
    // If n is even
    if (n % 2 == 0)
        return binomialCoeff(n, n / 2);
          
    // If n is odd
    else
        return binomialCoeff(n, (n + 1) / 2);
}
 
// Driver Code
let n = 4;
  
document.write(maxcoefficientvalue(n));
 
// This code is contributed by suresh07
 
</script>

Output:

Time complexity: O(n*n)

Auxiliary space: O(n*n)

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!