Counting Shortest Paths in Grids

It is well known that Pascal‟s triangle represents the binomial coefficients in binomial expansion. These numbers can also be interpreted as the numbers of (shortest) paths from the given position to top element of the triangle allowed to use two types of steps in these paths (left-up and right-up steps). 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 (paths with cityblock distance), 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 (paths with chessboard distance), the number of shortest paths can be described by trinomial coefficients. They can be obtained also in a triangle form by summing up three neighbour elements in the previous row. 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 from the position of the coefficient up to the top element of the triangle allowed to use n different types of steps, such that for trinomial coefficients, we use three types of steps, and quadrinomial coefficients we use four types of steps. We also present formulae to calculate trinomial, quadrinomial and n-nomial coefficients based on trinomial, quadrinomial 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 generalisations of the binomial coefficients. The number of shortest paths between any point pairs of the square grid, based on weighted distances, is computed. We use an 8-adjacency square grid, that is, a first weight is associated to the horizontal and vertical movements, while a second weight (not necessarily different from the first) is assigned to the diagonal steps. The chamfer distance of two points depends on the numbers and weights of the steps in a „shortest path‟. In special cases, as we have already mentioned, the cityblock and the chessboard distances, the two most basic and widely used digital distances of the two-dimensional digital space occur. Although our combinatorial result is theoretical, it is closely connected to applications, such as communication networks, path counting in digital images, traces and trajectories in 2D digital grids. We consider all the seven cases with non-negative weights and also the case when negative weights are allowed. Also, we will discuss the number of weighted shortest paths between any two pixels in the triangular grid, where the number of shortest paths depend on the values of α, β and γ weights. In the triangular grid for each pixel, we have three types of neighbourhood:1st, 2nd and 3rd neighbourhood, where we assign a weight for each neighbourhood type, and according to these weights, we use Chamfer distance to define these shortest paths, and we use combinations of absolute differences between pixels to define number of these paths. Keywords: Binomial Coefficients; Trinomial Coefficients; Quadrinomial Coefficients; n-nomial Coefficients; Multinomial Coefficients; Trajectories; Weighted Distances; Digital Distances; Combinatorics; Triangular Grid, Neighbourhood Types, Chamfer Distance; Shortest Weighted Paths; Path Counting.