POLYNOMIAL AND MULTINOMIAL COEFFICIENTS IN TERMS OF NUMBER OF SHORTEST PATHS

Abstract

The binomial coefficients show, in fact, the number of shortest paths in the square grid if only grid paths, i.e., paths on the grid lines, are allowed, and they also give the number of shortest paths in the hexagonal grid. When diagonal steps are also allowed in the square grid, the number of shortest paths can be described by trinomial coefficients. They form a triangle where three neighbour elements in the previous row are summed. We consider also further generalisations of such triangles and their elements, quadrinomial and n-nomial coefficients. In this context, n-nomial coefficients of n-nomial expansions represent the numbers of paths between the top and the actual position when n different types of steps are allowed to use, e.g., at trinomial coefficients three types of steps. Formulae to calculate trinomial, quadrominal and n-nomial coefficients are shown based on trinomial, quadrominal and n-nomial expansions, where the power of the sum of more than two items is computed, respectively. Multinomial expansions are also related. We give also a comparison of those values known as various ways of generalizations of the binomial coefficients.