Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Dynamic Programming
1.2.
Multiplicative Formula
1.3.
Binomial Coefficient
2.
Calculating Binomial Coefficients
2.1.
Recursive Method
2.2.
Factorial Method
2.3.
Multiplicative Method
2.4.
Dynamic Programming
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024

# nCr - Binomial Coefficient

## Introduction

Prerequisites: Permutations & Combinations

Consider the following problem - Find the number of ways to pick ‘K’ unordered items from a total of ‘N’ distinct items. For simplicity let us assume that K = 3 and N = 5. So, we can pick 3 items in the following ways:

1, 2, 3;  1, 2, 4;  1, 2, 5;  1, 3, 4;  1, 3, 5;  1, 4, 5;

2, 3, 4;  2, 3, 5;  2, 4, 5;

3, 4, 5;

Therefore, the total number of ways is 10. But how will we solve this problem for large values of K and N?

Let us try to break the problem into smaller subproblems. We have to calculate the number of ways to choose ‘K’ items from ‘N’ distinct items. We can break the problem into two parts -

1. The number of ways to choose ‘K’ items from the given set, such that we do not pick the last item.
2. The number of ways to choose ‘K’ items from the given set, such that we always choose the last item.

We can easily show that the answer of the 1st part + 2nd part will be the answer to the given problem since the last item will either be chosen or not chosen.

If we look more closely, the first part is the same as choosing K items from N-1 items since the last item is never chosen and the second part is the same as choosing K-1 items from N-1 items since the last element is always chosen.

Let us call the answer to the problem of choosing K items from N given items as F(N, K). Thus, using the above result, we can write:

F(N,K) = F(N-1, K) + F(N-1, K-1)

Now we have derived the formula to solve the given problem. We can easily write a recursive function that will compute the answer.

Base Case: F(N, 0) = 1, F(N, N) = 1.  There is only one way to choose 0 or N items from N given item.

### Dynamic Programming

The recursive code will have exponential time complexity. We can improve this by using dynamic programming. The idea is to store the values of F(N-1, K) and F(N-1, K-1) so that we can compute F(N, K) in constant time. DP[i][j] will store the answer of the number of ways of choosing j items from i items.

First, initialize a DP matrix of size N * K. Set dp[1][0] = 1 and dp[i][1] = 1. Then for all (2 <=i <= N) and (1 <= j <= K):

1. If j is not equal to 0, set dp[i][j] = dp[i-1][j] + dp[i-1][j-1].
2. Else set dp[i][j] = 0

In the end, dp[N][K] will store the value of F(N, K). This approach will have O(N * K) time complexity.

### Multiplicative Formula

``F(N, K) = N * (N - 1) * (N - 2)...(N - K + 1) / K * (K - 1) * (K - 2)...* 1``

This can also be written as -

``Factorial(N) / (Factorial(N - K) * Factorial(K))``

### Binomial Coefficient

Let us look at one another problem:

Consider the expansion of the equation - (1 + X) ^ N. What is the coefficient of X ^ K in the expansion?

In the problem have N terms of (1 + X) multiplied together, i.e, -

``(1 + X) * (1 + X) * (1 + X) * ….. N times``

We have to find the coefficient of X ^ K in the expansion of the above equation. Each (1 + X) term adds 1 to the power of X. Therefore, X ^ K will occur when we pick exactly K terms from the N terms of (1 + X). This is the same as the above problem and the answer will be F(N, K).

The expansion of (1 + X)^N can be written as:

``(1 + X) ^ N = F(N, 0) + F(N, 1) * X + F(N, 2) * X ^ 2 + ….  F(N, N) * X ^ N``

The number F(N, K) is also called the Binomial Coefficient since it occurs as a coefficient in the expansion of binomial expressions. These are also called nCr representing that we have to choose r items from n distinct items.

Also see, Euclid GCD Algorithm

## Calculating Binomial Coefficients

### Recursive Method

(Exponential Time Complexity)

``````Function NCR( N, K)
If K = N or K = 0
Return 0
Else
Return NCR(N - 1, K) + NCR(N - 1 + K - 1)``````

### Factorial Method

( O(N) time complexity )

``````Function Factorial(N)
Ans = 1
For i from 1 to N
Ans = Ans * i
Return Ans

Function NCR(N, K)
Return Factorial(N) / (Factorial(K)*(Factorial(N-K))``````

### Multiplicative Method

O(N) time complexity

(here Num represents Numenator and Den represents Denominator)

``````Function NCR(N, K)
Num = 1
Den = 1
For i from 1 to K
Num = Num * (N - i + 1)
Den = Den * i
Return Num / Den``````

### Dynamic Programming

O(N * K) time complexity

``````Function NCR(N, K)
Dp[N + 1][K + 1]
Dp[1][0] = 1, Dp[1][1] = 1
For i from 2 to N:
Dp[i][0] = 1
For j from 1 to K:
Dp[i][j] = Dp[i-1][j] + Dp[i-1][j-1]
Return Dp[N][K]``````

## FAQs

1. What are Binomial Coefficients?
Binomial coefficients are the number that appears as the coefficients in the expansion of a Binomial expression.

2. Where is Combination used?
Combinations are used when we have to select a group of something without considering the order in which we select them or their arrangement.

3. What is the formula to calculate C(N, R)?
Recursive: C(N, R) = C(N - 1, R) + C(N - 1, R - 1), Base Case: C(N, N)=1, C(N, 0)=1.
Factorial: C(N, R) = Factorial(N) / ( Factorial(R) * (Factorial(N - R) ).

## Key Takeaways

In this article, we learned what Binomial coefficients are, how they can be used to solve counting problems, and how to compute them. If you want to solve more such problems, you can visit Coding Ninjas Studio.

Read more: Recursion

If you think that this blog helped you share it with your friends!. To be more confident in data structures and algorithms, try out our DS and Algo Course.

Until then, All the best for your future endeavors, and Keep Coding.

Live masterclass