Binomial Coefficient - TutorialCup

Table of Contents

Problem Statement

Find the Binomial Coefficient for a given value of n and k.

“In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written as ${\tbinom {n}{k}}.$

Example

n = 5, k = 2

Explanation: Using the formula for calculation of binomial coefficient, we find 5 C 3 which is equal to 10.

What is Binomial Coefficient?

Before knowing how to find binomial coefficient. Let’s discuss briefly what is Binomial Coefficient? and why is it even required?

Because Binomial Coefficient is used heavily to solve combinatorics problems. Let’s say you have some n different elements and you need to pick k elements. So, if you want to solve this problem you can easily write all the cases of choosing k elements out of n elements. But this is a very time-consuming process when n increases. This problem can be easily solved using binomial coefficient. More than that, this problem of choosing k elements out of n different elements is one of the way to define binomial coefficient n C k. Binomial coefficient can be easily calculated using the given formula:

${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.$

Since now we are good at the basics, we should find ways to calculate this efficiently.

Naive Approach for finding Binomial Coefficient

This approach isn’t too naive at all. Consider you are asked to find the number of ways of choosing 3 elements out of 5 elements. So you can easily find n!, k! and (n-k)! and put the values in the given formula. This solution takes only O(N) time and O(1) space. But sometimes your factorial values may overflow so we need to take care of that. This approach is fine if we want to calculate a single binomial coefficient. But many times we need to calculate many binomial coefficients. So, it’s better to have them precomputed. We will find out how to find the binomial coefficients efficiently.

Optimized Approach for finding Binomial Coefficient

Well, naive approach was not naive if we wanted to find a single binomial coefficient. But when we need to find many binmoial coefficients. So the problem becomes difficult to complete in time limit. Because naive approach is still time consuming. So, here we have some queries where we are asked to calculate nCk for given n and k. There may be many queries. To solve this we should be familiar with Pascal’s Triangle. Cause that will make us understand much clearly why are we going to do what we are going to do.

Binomial Coefficient

Any cell in pascal triangle denotes binomial coefficients. We need to know some things regarding the Pascal’s triangle.

It starts with row 0.
Any number in Pascal’s triangle denotes binomial coefficient.
Any binomial coefficient which is not on the boundaries of the row is made from the summation of elements that are just above it in left and right direction.

${\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}}\quad {\text{for all integers }}n,k:1\leq k\leq n-1,$

Now we know that each binomial coefficient is dependent on two binomial coefficients. So if we can somehow solve them then we can easily take their sum to find our required binomial coefficient. So this gives us an intuition of using Dynamic Programming. Here the basecases are also very easily specified dp[0][0] = 1, dp[i][0] = dp[i][[i] = 1.

Code

C++ code for finding Binomial Coefficient

#include<bits/stdc++.h>
using namespace std;

int C[51][51];

// this function just makes our pascal triangle
void precomputeBinomialCoefficients()
{

  for (int i = 0; i <= 50; i++)
  {
    for (int j = 0; j <= i; j++)
    {
      // Base Cases
      if (j == 0 || j == i)
        C[i][j] = 1;
      else
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; // use recursive formula
    }
  }
}

int main()
{
  // precomputationis being done for n = 50, you can change the value of n
  precomputeBinomialCoefficients();
  int noOfQueries;cin>>noOfQueries;
  while(noOfQueries--){
    // here n & k do not satisfy the propertoes of binomial coefficient
    // then we will answer it as 0
    int n,k;cin>>n>>k;
    if(n<=50 && k<=50)
      cout<<C[n][k]<<endl;
    else
      cout<<0<<endl;
  }
}

10
10
15

Java Code to find Binomial Coefficient

import java.util.*;

class Main{
  static int C[][];

  // this function just makes our pascal triangle
  static void precomputeBinomialCoefficients() 
  {
    for (int i = 0; i <= 50; i++) 
    { 
      for (int j = 0; j <= i; j++) 
      { 
        // Base Cases 
        if (j == 0 || j == i) 
          C[i][j] = 1; 
        else
          C[i][j] = C[i - 1][j - 1] + C[i - 1][j]; // use recursive formula
      } 
    }	
  } 

  public static void main(String[] args)
  {
    C = new int[51][51];
    // precomputationis being done for n = 50, you can change the value of n
    precomputeBinomialCoefficients();
    Scanner sc = new Scanner(System.in);
    int noOfQueries;
    noOfQueries = sc.nextInt();
    while(noOfQueries-- > 0){
      // here n & k do not satisfy the propertoes of binomial coefficient
      // then we will answer it as 0
      int n = sc.nextInt();
      int k = sc.nextInt();
      if(n<=50 && k<=50)
        System.out.println(C[n][k]);		
      else
        System.out.println(0);
    }
  }
}

10
10
15

Complexity Analysis

Time Complexity

O(N^2 + Q), because we are precomputing the binomial coefficients up to nCn. This operation takes O(N^2) time and then O(1) time to answer each query.

Space Complexity

O(N^2), for storing the precomputed results of binomial coeffcients.