Recursive Computation of Binomial and Multinomial Coefficients and Probabilities

This chapter studies a prominent class of recursively-defined combinatorial functions, namely, the binomial and
multinomial coefficients and probabilities. The chapter reviews the basic notions and mathematical definitions
of these four functions. Subsequently, it characterizes each of these functions via a recursive relation that is
valid over a certain two-dimensional or multi-dimensional region and is supplemented with certain boundary
conditions. Visual interpretations of these characterizations are given in terms of regular acyclic signal flow
graphs. The graph for the binomial coefficients resembles a Pascal Triangle, while that for trinomial or
multinomial coefficients looks like a Pascal Pyramid, Tetrahedron, or Hyper-Pyramid. Each of the four
functions is computed using both its conventional and recursive definitions. Moreover, the recursive structures
of the binomial coefficient and the corresponding probability are utilized in an iterative scheme, which is
substantially more efficient than the conventional or recursive evaluation. Analogous iterative evaluations of the
multinomial coefficient and probability can be constructed similarly. Applications to the reliability evaluation
for two-valued and multi-valued k-out-of-n systems are also pointed out.