Play With Binomial coefficient

Binomial Series has Very important role in mathematics .
Today we are going to discuss different approach of finding binomial coefficient .

Lets Start With Basic Approach 

Mathematical Formula to find binomial Coefficient 

Directly implement this mathematical formula  to find Binomial Coefficient 


C-Program:

1. //Direct Approach to find Binomial Coefficient 
2. //Beginner 2 Computer Science 
3. #include<stdio.h>
4. #include <string.h>
6. int BinomialCoeff(int n,int r){
7.         /*
8.            Direct Approach
9.            coeff=n!/((n-r)! * r!)
10.            !-> stands for factorial
11.            ie. 5!= 5*4*3*2*1
12.         */
13.         int max(int a,int b){
14.                 if(a>b)
15.                     return a;
16.                 else
17.                     return b;
18.         }
19.         int min(int a,int b){
20.                 if(a<b)
21.                     return a;
22.                 else
23.                     return b;
24.         }
25.        
26.         int i,mx,mn;
27.         int coeff=1;
28.         //nC0 & nCn
29.         if(r==0 ||n==r)
30.             return 1;
31.            
32.         mx=max((n-r),r); //max of r & n-r
33.         mn=min((n-r),r); //min of r & n-r
34.        
35.         //calculating coeff=n!/mx!
36.         for(i=mx+1;i<=n;i++){
37.                 coeff=coeff*i;
38.         }
39.        
40.         //calculate coeff=coeff/mn!
41.         for(i=2;i<=mn;i++){
42.                 coeff=coeff/i;
43.     }
44.         return coeff;
45. }
47. int main()
48. {
49.   int n=5,r=3;
50.   printf("==> %d\n",BinomialCoeff(n,r));
51.   return 0;
52. }

Recursive Approach :

Recursive Approach to calculate binomial Coefficient

Recursion Tree for Binomial Coefficient

C-Program for Finding Binomial Coefficient using recursive Approach :

1. //Recursive Approach for finding Binomial Coefficient
2. //C99 Program 
3. #include<stdio.h>
4. #include <string.h>
6. int BinomialCoeff_Recur(int n,int r){
7.         /*
8.           recursive Approach
9.           when r=0 or r==n return 1 //base case
10.           else coeff=coeff=coeff+BinomialCoeff_Recur(n-1,r)+BinomialCoeff_Recur(n-1,r-1);
11.           return coeff
12.         */
13.         int coeff=0;
14.        
15.         if(r<=0 || r==n){ //termination case
16.                 return 1;
17.         }
18.         if(r<n ){
19.              //recursive call
20.             coeff=coeff+BinomialCoeff_Recur(n-1,r)+BinomialCoeff_Recur(n-1,r-1);
21.         }
22.         return coeff;
23. }
25. int main()
26. {
27.   int n=5,r=3;
28.   printf("==> %d\n",BinomialCoeff_Recur(n,r));
29.   return 0;
30. }

Dynamic Programming Approach:

We gonna use bottom top approach & store result which may need in future .

Dynamic Programming Approach for finding Binomial Coefficient

C-Program for finding Binomial Coefficient using Dynamic Programming Approach:

1. //Dynamic Programming Approach for finding Binomial Coefficient 
2. // C Program
3. //Beginner 2 Computer Science
4. #include<stdio.h>
5. #include<string.h>
7. int BinomialCoeff_DynamicProgramming(int n,int r){
8.         /*
9.         **** this code is for C99
10.         ******Need <string.h>
11.         Need To fallow bottom top approch
12.         & Store value of each calcution may need in future
13.         */
14.         int min(int a,int b){
15.                 if(a<b)
16.                     return a;
17.                 else
18.                     return b;
19.         }
20.        
21.         int mtrx[n+1][r+1];
22.         int i,j;
23.        
24.         if(n==r || r==0){ //Special Case
25.                 return 1;
26.         }
27.         else if(r>n){
28.                 return 0;
29.         }
30.        
31.         //This is Special Fuction Supported in C99
32.         memset(mtrx,0,sizeof(mtrx)); //now for all i,y mtrx[i][j]=0
33.        
34.         //Calculation for binomial coefficient
35.         for(i=0;i<=n;i++){
36.                 for(j=0;j<=min(i,r);j++){
37.                         if(j==0 || j==i)
38.                             mtrx[i][j]=1;
39.                         else
40.                             mtrx[i][j]=mtrx[i-1][j-1]+mtrx[i-1][j];
41.                 }
42.         }
43.         return mtrx[n][r];
44. }
46. int main()
47. {
48.   int n=5,r=3;
49.   printf("==> %d\n",BinomialCoeff_DynamicProgramming(n,r));
50.   return 0;
51. }

Please Suggest if Found Any Bug
Thank U