How to Calculate Binomial Coefficients, nCr

We used a simple function to calculate nCr in an earlier program to display Pascal's Triangle. It shows the values of binomial coefficients upto n=12. We then used a more efficient algorithm to display Pascal's Triangle. Let us now use a more efficient program to find single binomial coefficients. Here is how we can do this.

• We add read statements to read values of n and r at the time of execution. We can also add a GOTO statement to read new values.
• We add an integer function o calculate nCr. For this, we need to set nCr when n=r as 1. i.e.nCn=1. This also true for 0C0. Similarly, we set nC0=1.
• Next, we need to run a DO loop to calculate the factorial in the numerator. No, wait a minute. This calculation can be made a little simpler. As we know, n>r for all the n,r pairs after having dealt with trivial cases above. Therefore, r! and (n-r)! will already be included in n!. We can, therefore, simplify calculations as shown in the picture. Here you go.
  

  

  Simplified Formula for nCr used in the Program

Now for the Fortran program,

 !Program to find nCr
program Combinations
    implicit none
    integer n,r,cont
  
    10 write (*,*) "Give the value of n (the total no. of objects)"
    read (*,*) n
  
    write (*,*) "Give the value of r (the number of objects selected at a time)"
    read (*,*) r
  
    write (*,*) "Calculating the total number of possible combinations"
    write(*,20) n,"C",r,"= ",nCr (n,r)
    write(*,*)
    20 format (i10,a,i10,a,i10) !You can alter the format as per your requirement
  
    write(*,*) "Press 1 to continue. Press 2 to exit" !To read more values. Optional
    read (*,*) cont
    write(*,*)
    write(*,*)
    if (cont==1) then
        goto 10
          else
        stop
    end if
 
    contains
  
        integer function nCr (n,r)
            integer n,r,i, Numer,Denom, large,small
            if (n==r) then
                nCr=1
                else if (r==0) then
                nCr=1
                else if (r.lt.(n-r)) then
                 small=r
                 large=n-r
                 else
                 large=r
                small=n-r
            end if
          
            Numer=n
            do i=n-1,(large+1),-1 !To save you the trouble of calculating lengthy factorials
                Numer=Numer*i
            end do
          
            Denom=small
            do i=small-1,2,-1
                Denom=Denom*i
               end do
          
            nCr=Numer/Denom
          
        end function
  
end program Combinations

Sample Output. You can get all values upto n=17. Beyond that, you can still get results if r is not close to n/2, which results in very large values (around the middle of a row in Pascal's triangle).