Recursive Computation of Binomial and Multinomial Coefficients and Probabilities | Chapter 07 | Advances in Mathematics and Computer Science Vol. 1
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.
Author Details:
Ali Muhammad Ali Rushdi
Department
of Electrical and Computer Engineering, King Abdulaziz University, P.O.Box
80204, Jeddah, 21589, Kingdom of Saudi Arabia.
Mohamed Abdul Rahman
Al-Amoudi
Department
of Electrical and Computer Engineering, King Abdulaziz University, P.O.Box
80204, Jeddah, 21589, Kingdom of Saudi Arabia.
View Volume: https://doi.org/10.9734/bpi/amacs/v1
Comments
Post a Comment