Binomial Coefficient

Binomial Coefficient is represented by nCk which means number of ways of choosing k objects from n objects.It is the coefficient of x^k term in the polynomial expansion of (1+x)^n.It also represents an entry in Pascals Triangle.

Properties-

1. nCk=(n!)/[(k!)*(n-k)!]
2. nCn=1
3. nC0=1
4. nCk=(n-1)C(k)+(n-1)C(k-1)
5. nCk=(n)C(n-k)

The task is to find the value of nCk given the values of n and k.

Recursive solution-

int binomialCoeff(int n, int k)
{
  // Base Cases
  if (k==0 || k==n)
    return 1;

  // Recurrence
  return  binomialCoeff(n-1, k-1) + binomialCoeff(n-1, k);
}

For large values of n,there will be many common subproblems.For example-
To calculate 5C2,function will be called for 4C2 and 4C1.
To calculate 4C1,function will be again called for 3C0 and 3C1.
To calculate 4C2,function will be called for 3C1 and 3C2.
So,3C1 is being calculated twice.
This problem has overlapping sub-problems property.Re-computation of same sub-problems can be avoided by constructing a temporary array C[][] and storing the results like we do in other dynamic programming problems.

DP based solution-

//C[][] is the temp array

 for(i=0;i<=n;i++)
    {

                     for(j=0;j<=i;j++)
                     {

  //base condition
    if((i==0)||(j==0))  C[i][j]=1;   
  
    else C[i][j]=C[i-1][j-1]+C[i-1][j];
}
}
//C[n][k] gives the result

Time Complexity of this code is O(n*k).

Note-

n,k are non negative integers.
nCk is valid only for n>0 and 0<=k<=n.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

* Copy This Password *

* Type Or Paste Password Here *

43,751 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>