Factorial and Combinatorial Coefficient

Factorial and Combinatorial Coefficient


Problem Statement

The combinatorial coefficient C(n,r) is defined as follows:

where 0 <= r <= n must hold. Write a module that contains two functions: (1) Factorial() and (2) Combinatorial(). The former computes the factorial of its argument, while the latter uses the former to compute the combinatorial coefficient. Then, write a main program that uses this module. 

Solution

The following is the desired module:

! --------------------------------------------------------------------
! MODULE FactorialModule
! This module contains two procedures: Factorial(n) and
! Combinatorial(n,r). The first computes the factorial of an integer
! n and the second computes the combinatorial coefficient of two
! integers n and r.
! --------------------------------------------------------------------

MODULE FactorialModule
IMPLICIT NONE

CONTAINS

! --------------------------------------------------------------------
! FUNCTION Factorial() :
! This function accepts a non-negative integers and returns its
! Factorial.
! --------------------------------------------------------------------

INTEGER FUNCTION Factorial(n)
IMPLICIT NONE

INTEGER, INTENT(IN) :: n ! the argument
INTEGER :: Fact, i ! result

Fact = 1 ! initially, n!=1
DO i = 1, n ! this loop multiplies
Fact = Fact * i ! i to n!
END DO
Factorial = Fact

END FUNCTION Factorial

! --------------------------------------------------------------------
! FUNCTION Combinarotial():
! This function computes the combinatorial coefficient C(n,r).
! If 0 <= r <= n, this function returns C(n,r), which is computed as
! C(n,r) = n!/(r!*(n-r)!). Otherwise, it returns 0, indicating an
! error has occurred.
! --------------------------------------------------------------------

INTEGER FUNCTION Combinatorial(n, r)
IMPLICIT NONE

INTEGER, INTENT(IN) :: n, r
INTEGER :: Cnr

IF (0 <= r .AND. r <= n) THEN ! valid arguments ?
Cnr = Factorial(n) / (Factorial(r)*Factorial(n-r))
ELSE ! no,
Cnr = 0 ! zero is returned
END IF
Combinatorial = Cnr

END FUNCTION Combinatorial

END MODULE FactorialModule

Click here to download this program.

Here is the main program:

! --------------------------------------------------------------------
! PROGRAM ComputeFactorial:
! This program uses MODULE FactorialModule for computing factorial
! and combinatorial coefficients.
! --------------------------------------------------------------------

PROGRAM ComputeFactorial
USE FactorialModule ! use a module

IMPLICIT NONE

INTEGER :: N, R

WRITE(*,*) 'Two non-negative integers --> '
READ(*,*) N, R

WRITE(*,*) N, '! = ', Factorial(N)
WRITE(*,*) R, '! = ', Factorial(R)

IF (R <= N) THEN ! if r <= n, do C(n,r)
WRITE(*,*) 'C(', N, ',', R, ') = ', Combinatorial(N, R)
ELSE ! otherwise, do C(r,n)
WRITE(*,*) 'C(', R, ',', N, ') = ', Combinatorial(R, N)
END IF

END PROGRAM ComputeFactorial

Click here to download this program. 

Program Input and Output

The following is the output from the above program.

Two non-negative integers -->
13 4
13! = 1932053504
4! = 24
C(13,4) = 221


Discussion

  • The computation of combinatorial coefficients has been discussed in an programming example, where functions Cnr(n,r) and Factorial(k) are internal functions of the main program.
  • In this version, functions Factorial(n) and Combinatorial(n,r) are moved to a module called FactorialModule as internal functions of that module.
  • Factorial(n) takes a non-negative integer and returns its factorial.
  • Combinatorial(n,r) takes two non-negative integers n and r. If 0 <= r <= n, the combinatorial coefficient C(n,r) is returned; otherwise, 0 is returned.
  • Note that in module FactorialModule, there is no variables global to its internal functions. All internal functions use their own internal (or local) variables.
  • This module does not perform many checks as in a previous programming example. But, it is not difficult to add these tests.
  • After moving the computation functions to a module, the main program becomes simpler. In the beginning, the main program must USES FactorialModule so that functions Factorial() and Combinatorial() can be accessed from within the main program.
  • The main program reads in values for n and r. If r <= n, the combinatorial coefficient C(n,r) is computed by calling Combinatorial(n,r); otherwise, the main program computes Combinatorial(r,n).
  • If the main program and module FactorialModule are stored in files fact-1p.f90 and fact-m.f90, respectively, then you can compile them together with the following command:
    f90 fact-m.f90 fact-1p.90

    or with the following that generates an executable called fact1p:

    f90 fact-m.f90 fact-1p.90 -o fact-1p

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s