Binomial coefficients
Introduction
Binomial coefficients are mathematical entities that arise in combinatorics, probability theory, and algebra. The binomial coefficient n choose k
represents the number of ways to choose k elements from a set of n elements without regard to order. The algorithm we will discuss computes the binomial coefficient using a combinatorial formula that iteratively multiplies the numerator by n  i and the denominator by i + 1, starting from 1 and going up to the smaller of k and n  k.
Implementation
(* Evaluate binomial coefficients *)
let binomialCoeff n p =
let p = if p < n . p then p else n . p in
let rec cm res num denum =
if denum <= p then cm ((res *. num) /. denum) (num . 1.) (denum +. 1.)
else res in
cm 1. n 1.
The binomial coefficient algorithm takes two arguments: n
and p
. It calculates the binomial coefficient of n
and p
. It first computes the minimum of p
and n  p
, then initializes variables res
, num
, and denum
and passes them to a helper function cm
.
cm
takes a result res
, a numerator num
, and a denominator denum
and iteratively multiplies res
by num
and divides by denum
, decrementing num
and incrementing denum
until denum
is greater than p
. The final result of cm
is the binomial coefficient of n
and p
.
Stepbystep Explanation

Check if
p
is greater thann  p
. If it is, setp
ton  p
to reduce the number of computations. This is becausen choose k
is equivalent ton choose nk
, andk
must be no greater thann / 2
. 
Initialize a result variable
res
to 1, a numerator variablenum
ton
, and a denominator variabledenum
to 1. 
Pass
res
,num
, anddenum
to a helper functioncm
. 
In
cm
, calculateres * num / denum
and assign tores
. 
Decrement
num
by 1 and incrementdenum
by 1. 
If
denum
is less than or equal top
, recurse by callingcm
withres
,num
, anddenum
as arguments. 
If
denum
is greater thanp
, returnres
as the binomial coefficient ofn
andp
.
Complexity Analysis
The algorithm performs a constant amount of initialization before calling the helper function cm
. The helper function cm
performs p
iterations, each of which performs one multiplication and one division. Therefore, the time complexity of the algorithm is O(p), where p
is the smaller of p
and n  p
.
The space complexity of the algorithm is O(1), as it only initializes a constant number of variables regardless of the input size.