Counting Shortest Paths in Grids

Abstract

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.

ÖZ: Pascal üçgeninin binom açılımındaki binom katsayılarını temsil ettiği iyi bilinmektedir. Bu sayılar, aynı zamanda, bu konumlarda iki tür adım (sol-yukarı ve sağ-yukarı adımlar) kullanılmasına izin verilen, verilen konumdan üçgenin üst elemanına kadar (en kısa) yolların sayısı olarak da yorumlanabilir. Binom katsayıları, aslında sadece ızgara yollarının, yani ızgara çizgilerindeki yollara (şehir bloğu uzaklığına sahip yollar) izin verilirse, kare ızgaradaki en kısa yolların sayısını gösterir ve ayrıca altıgen ızgaradaki en kısa yolların sayısını verir. Kare ızgarada (satranç tahtası uzaklıklı yollar) köşegen adımlara da izin verildiğinde, en kısa yolların sayısı üçlü katsayılarla tanımlana bilir. Bir önceki satırda üç komşu elemanı toplayarak üçgen şeklinde de elde edilebilirler. Bu tür üçgenlerin ve elemanlarının, kuadrinomiyal ve n-nominal katsayıların daha fazla genelleştirilmesini de düşünüyoruz. Bu bağlamda, n-nomal açılımların n-nomal katsayıları, katsayı pozisyonundan üçgenin üst elemanına kadar n farklı tipte adım kullanılmasına izin verilen yolların sayısını temsil eder, böylece üçlü katsayılar için üç adım türleri ve dört adım katsayısı dört tür adım kullanırız. Ayrıca, ikiden fazla öğenin toplamının kuvvetinin hesaplandığı üçlü, dörtlü ve n-nomiyal açılımlara dayanan üçlü, dörtlü ve n-nomal katsayıları hesaplamak için formüller sunuyoruz. Çok terimli açılımlar da ilişkilidir. Ayrıca binom katsayılarının çeşitli genelleme yöntemleri olarak bilinen değerlerin bir karşılaştırmasını da veriyoruz. Ağırlıklı mesafelere göre kare ızgaranın herhangi bir nokta çifti arasındaki en kısa yolların sayısı hesaplanır. 8-komşu kare ızgara kullanıyoruz, yani bir ilk ağırlık yatay ve dikey hareketlerle ilişkiliyken, ikinci bir ağırlık (birinciden farklı olması gerekmez) köşegen adımlara atanmıştır. İki noktanın chamfer uzaklığı, 'en kısa yoldaki' adımların sayılarına ve ağırlıklarına bağlıdır. Özel durumlarda, daha önce de belirttiğimiz gibi, şehir bloğu ve satranç tahtası mesafeleri, iki boyutlu dijital alanın en temel ve yaygın olarak kullanılan iki dijital mesafesi meydana gelir. Kombinatorik sonucumuz teorik olmasına rağmen, iletişim ağları, dijital görüntülerde yol sayma, 2D dijital ızgaralardaki izler ve yörüngeler gibi uygulamalarla yakından bağlantılıdır. Negatif olmayan ağırlıkları olan yedi durumu ve negatif ağırlığa izin verilen durumu da ele alıyoruz. Ayrıca, α, β ve γ ağırlıklarının değerlerine bağlı olarak en kısa yol sayısının olduğu üçgen ızgaradaki herhangi iki piksel arasındaki ağırlıklı en kısa yolların sayısını tartışacağız. Her piksel için üçgen ızgarada, üç tip komsuluk var: her komsuluk tipi için bir ağırlık atadığımız 1., 2. ve 3. komsuluk ve bu ağırlıklara göre, bu en kısa yolları tanımlamak için Chamfer mesafesini kullanıyoruz ve biz bu yolların sayısını tanımlamak için pikseller arasındaki mutlak farklılıkların kombinasyonlarını kullandık. Anahtar Kelimeler: Binom Katsayıları; Trinomiyal Katsayılar; Dörtlü Katsayıları; n-nominal Katsayıları; Çok Terimli Katsayılar; Yörüngeleri; Ağırlıklı Mesafeler; Dijital Mesafeler; Bir Kombinasyon; Üçgen Izgara, Komşuluk Tipleri, Chamfer Mesafesi; En Kısa Ağırlıklı Yollar; Yol Sayımı.