Trajectories and Traces on Non-traditional Regular Tessellations of the Plane

Abstract

In this paper, shortest paths on two regular tessellations, on the hexagonal and on the triangular grids, are investigated. The shortest paths (built by steps to neighbor pixels) between any two points (cells, pixels) are described as traces and generalized traces on these grids, respectively. In the hexagonal grid, there is only one type of usual neighborhood and at most two directions of the steps are used in any shortest paths, and thus, the number of linearizations of these traces is easily computed by a binomial coefficient based on the coordinate differences of the pixels. Opposite to this, in the triangular grid the neighborhood is inhomogeneous (there are three types of neighborhood), moreover this grid is not a lattice, therefore, the possible shortest paths form more complicated sets, a kind of generalized traces. The linearizations of these sets are described by associative rewriting systems, and, as a main combinatorial result, the number of the shortest paths are computed between two triangles, where two cells are considered adjacent if they share at least one vertex.

1 Introduction

In 1977, analyzing basic networks, Mazurkiewicz introduced the concept of partial commutations. Two independent parallel events commute, i.e., their executing order can be arbitrary in a sequential simulation. By using the concept of commutations, the work of the concurrent systems can be described by traces. In these systems some (pairs of) elementary processes (i.e., atomic actions; they are represented by the letters of the alphabet) may depend on each other, and some of them can be pairwise independent. The order of two consecutive independent letters can be arbitrary, in this way the traces are a kind of generalizations of words. Traces and trace languages play important roles in describing parallel events and processes. An automata theoretic approach on rational trace languages can be found in [18, 21], and in [19, 20] for context-free trace languages. Actually, linearizations of trace languages, that are sets of words representing traces of the trace languages, are accepted by various type of automata. A special two-dimensional representation of some traces is given by trajectories on the square grid. These trajectories were also used to describe syntactic constraints for shuffling two parallel events described by words in [9]. Trajectories on other regular grids could also play a somewhat similar important role. A kind of generalization of traces is presented in [7], where apart from the usual permutation rules, some other rewriting rules are also allowed. We show that the sets of shortest paths in the triangular grid can be seen as generalized traces.

Considering the set of (types and directions of the) possible steps as the alphabet, a path, a sequence of steps, is actually a word. This gives the link between formal languages, trace theory and digital geometry.

Path counting, an interesting and important technique in digital geometry and in digital image processing, was invented in [23]. The number of shortest paths on the square grid was computed by an algorithm in [1], while recursive formulae were given in [2]. The square grid is counted as the traditionally used tessellation of the plane. There are other two regular tessellations, namely, the hexagonal and the triangular grids. They are usually called non traditional or unconventional grids, since they are less used in practice. On the other side they have more symmetries and more interesting combinatorial structures than the square grid has. In several cases they proved to be more efficient in applications as well. Recently, in [4], counting the shortest paths based on the two closest types of neighborhood on the triangular grid was also considered. In this paper, these two non-traditional but regular tessellations of the two-dimensional plane are used. They are duals of each other in graph theoretic sense. The main achievements of this work are the following ones: The shortest paths between any two pixels of these grids are described as (generalized) traces and the number of the shortest paths are computed by enumerative combinatorial techniques. As we will see, the case of the hexagonal grid is very simple, it is, actually, shown only for the analogy. The shortest paths between two hexagons form a trace, in which the order of the two types of steps can be arbitrary. The triangular grid is not a lattice, therefore, as we will see, the shortest paths based on the third widely used neighborhood (that is each pixel having 12 neighbors) form more complicated sets. We also present formulae to compute the number of shortest paths, in this way complementing the results of [4].

We note here that various digital, i.e., path based distances are investigated for the triangular grid, e.g., distances by neighborhood sequences [10, 11, 14] and weighted distances [16]. In this paper, we use one of the most natural digital distance functions which is a special case of the previously mentioned distance functions. Nevertheless, it already has very interesting theoretical, combinatorial properties, as we will see later on.

We assume that the readers are familiar with traces and rewriting systems, otherwise they are referred to, e.g., [3, 6, 24]. As usual, in this paper, the traces are also represented by sets of words.

2 Traces and Trajectories on the Hexagonal Grid

The hexagonal grid can be elegantly described by three coordinates such that every hexagon has a unique triplet with 0-sum [5], see Fig. 1: formally, the (set of pixels of the) hexagonal grid can be described as $\{p(p(1),p(2),p(3))~|~p(1),p(2),$ $p(3)\in \mathbb Z, p(1)+p(2)+p(3)=0 \}$. Consequently, by stepping from a pixel to a neighbor one, two of the coordinate values are changing by $\pm 1$. This formulation coincides the well known and widely used concept of neighbor pixels. (On the hexagonal grid two pixels are neighbors if they share a side of a hexagon, see, e.g., the pixels $(-2,0,2)$ and $(-2,1,1)$ on Fig. 1. Actually, the same neighborhood concept for the hexagons is resulted if it is required to share at least one point on their border.) A path connects two pixels by a sequence of neighbor pixels. The (digital) distance of two pixels is the length, that is the number of steps, of a/the shortest path between them. It is easy to prove (see, e.g., [8, 11]) that the distance, i.e., the number of steps in a/the shortest path, of any two pixels can be computed as

$$d(p(p(1),p(2),p(3)),q(q(1),q(2),q(3))) =\max \nolimits _{i\in \{1,2,3\}}\{|p(i)-q(i)|\}.$$

Fig. 1.

A part of the hexagonal grid with a symmetric coordinate frame.

A (hexagonal stepping) lane is a set of pixels with a fixed coordinate value, e.g., $y=-1$ for the top hexagons on Fig. 1. One can very easily generate a shortest path connecting the two given pixels p and q: if they share a coordinate value, i.e., $p(i)=q(i)$ (for any $i\in \{1,2,3\}$), then keeping that coordinate value fixed, the pixels can be connected through a lane [11, 17], i.e., by the pixels of $\{ r(r(1),r(2),r(3)) ~|~ r(i)=p(i), \min \{p(j),q(j)\} \le r(j) \le \max \{p(j),q(j)\}, j\ne i \}$. If there is no shared coordinate, then let $i\in \{1,2,3\}$ be a value such that $|p(i)-q(i)| \ge |p(j)-q(j)|$ for every $j\in \{1,2,3\}$, then a shortest path is the concatenation of the paths connecting, e.g., p to r and r to q with $r(j)=p(j)$, $r(k)=q(k)$, $r(i)=-p(j)-q(k)$ where i, j, k are pairwise different elements of $\{1,2,3\}$. In the next section we show how the number of shortest paths can be computed.

2.1 Number of Shortest Paths on the Hexagonal Grid

Since the hexagonal grid is a lattice, one can step from any pixel to any of the six directions. Thus the order of the steps in a shortest path is not important, the reached pixel depends on only their respective numbers. Using the alphabet $\varSigma = \{\rightarrow , \searrow , \swarrow , \leftarrow ,\nwarrow , \nearrow \}$ for the steps in the six directions, each letter is independent of each other, therefore one can freely move (permute) them in a path. One can observe that shortest path contains at most two distinct letters and their numbers are determined by the coordinate differences of the pixels. Therefore, we can state the following result that can be proven by elementary combinatorics.

Theorem 1

The number of shortest paths between p and q is given by the binomial coefficient

$$ \left( {\begin{array}{c}\max _i\{|p(i)-q(i)|\}\\ \min _i\{|p(i)-q(i)|\}\end{array}}\right) .$$

Actually, an equivalence set of shortest paths is the commutative closure of any singleton language of a shortest path, i.e., these traces are based on the maximal independency relations (commutations): instead of the words, their Parikh-vectors [22], the multiset of their letters can be used to describe shortest paths as traces on the hexagonal grid.

As the main contribution of the paper a similar question is answered: it is shown how the number of shortest paths can be counted on the triangular grid (based on neighborhood relation of 12 neighbors).

3 Preliminaries: Description of the Triangular Grid

The triangular grid, preserving the symmetry of the grid, can also be described by three integer coordinates [10, 11, 25]. There are two types of pixels (by orientation): the even pixels have zero-sum triplets, while the odd pixels have one-sum triplets. The neighborhood relations are formally defined: Let p(p(1), p(2), p(3)) and q(q(1), q(2), q(3)) be two pixels, they are m-neighbors ($m\in \{1,2,3\}$) if

• $|p(i)-q(i)| \le 1$, for $i \in \{1,2,3\}$, and

• $|p(1)-q(1)| + |p(2)-q(2)| + |p(3)-q(3)| = m$.

Two pixels are neighbors, if they are m-neighbors for some $m\in \{1,2,3\}$. Various neighborhoods and the coordinate system used are shown in Fig. 2. The set of pixels sharing a fixed coordinate is called a lane, e.g., $y=-2$ for the topmost pixels of Fig. 2. Paths, their lengths and distances of pixels are also defined analogously to the hexagonal case.

Fig. 2.

A part of the triangular grid with coordinate values (left) and various neighborhood of an even pixel (right).

A step to a 2-neighbor does not modify the parity, while step to a 1-neighbor or a 3-neighbor pixel changes (inverts) the parity. The basic motions, the possible steps form our alphabet: Let $\varSigma =\{\uparrow _1, \downarrow _1, \nwarrow _1, \searrow _1, \nearrow _1, \swarrow _1, \leftarrow _2,\rightarrow _2, \nwarrow _2, \searrow _2, \nearrow _2,$ $\swarrow _2, \uparrow _3, \downarrow _3, \nwarrow _3, \searrow _3, \nearrow _3, \swarrow _3 \}$. The arrows show the directions, while the indices indicate the used neighborhood of the given step. The steps, the letters of the alphabet correspond to grid-vectors:

For any two pixels p(p(1), p(2), p(2)) and q(q(1), q(2), q(3)), their respective positions and their shortest paths are isometrically transformed, and, therefore, their distance is kept by using the following transformations of the grid (see [15] for details).

• If p is an odd pixel, then by a mirroring both p and q to the center of the edge shared by the pixels (0, 0, 0) and (0, 1, 0) one obtains $p'(-(p(1)-1),-p(3),-p(2))$ and $q'(-(q(1)-1),-q(3),-q(2))$ (By this transformation the parities of the pixels are also changed.)

• If p is an even pixel, then by a translation one can obtain $p'(0,0,0)$ and $q'(q(1)-p(1),q(2)-p(2),q(3)-p(3))$.

• Now, let p be the origin and let q be a pixel such that $i\in \{1,3\}$ is the direction for which $|q(i)| \ge |q(j)|$ for any $j\in \{1,2,3\}$. Then the mirroring to the axis corresponding to the direction $k\in \{1,3\}$ such that $k\ne i$ transforms q to $q'$ such that $q'(2)=q(j), q'(j)=q(2), q'(k)=q(k)$. (The image of the origin is itself.)

Based on the previous transformations, w.l.o.g., we can assume that p is the origin (0, 0, 0), i.e., further in this paper, we measure the distance, the shortest paths from the origin to any pixel q of the grid with the following property: the second coordinate of q has the largest absolute value among its coordinates, i.e., $|q(2)|\ge |q(1)|$ and $|q(2)|\ge |q(3)|$. Pixels q with this property form the analyzed part of the grid.

In the next subsection we give a shortest path from the origin to any pixel q with the above property based on a greedy algorithm.

3.1 A Shortest Path

We refer to [10, 11] for the detailed description of a more general algorithm (using various digital distances based on neighborhood sequences) that provides a shortest path; it can be applied for our case using any type of the defined neighborhoods in each step: in terms of neighborhood sequences, it can be written as a sequence with only 3’s meaning that every type of neighbors is allowed in each step. In this section we provide a shortest path from the origin to any pixel of the analysed part.

Proposition 1

Let q(q(1), q(2), q(3)) be an even pixel such that $|q(2)|\ge |q(1)|$ and $|q(2)|\ge |q(3)|$.

• If $q(2)>0$, then a shortest path from (0, 0, 0) to q is obtained as the concatenation of $-q(1)$ $\swarrow _2$ steps and $-q(3)$ $\searrow _2$ steps: $\swarrow _2^{|q(1)|} \searrow _2^{|q(3)|}$.

• If $q(2)<0$, then a shortest path from (0, 0, 0) to q is obtained as the concatenation of q(3) $\nwarrow _2$ steps and q(1) $\nearrow _2$ steps: $\nwarrow _2^{|q(3)|} \nearrow _2^{|q(1)|}$.

Proof

Let q(q(1), q(2), q(3)) be an even pixel such that $|q(2)|\ge |q(1)|$ and $|q(2)|\ge |q(3)|$.

We show a formal proof for the case $q(2)>0$; a similar proof suffices for the other case.

Thus q has the coordinate values, (q(1), q(2), q(3) with $q(1)\le 0$ and $q(3)\le 0$ and $q(2)=|q(1)|+|q(3)|$.

Then, a shortest path from (0, 0, 0) to q cannot have a length less than q(2) since in every step a coordinate value is changed by at most 1.

Let us consider the path consisting of $-q(1)$ $\swarrow _2$ steps and then $-q(3)$ $\searrow _2$ steps. The path $\swarrow _2^{|q(1)|} \searrow _2^{|q(3)|}$ is a valid path, since steps to 2-neighbors are allowed at any pixels (and thus, also in even pixels). Using the coordinate representations of the steps: from (0, 0, 0), it goes through on $(-1,1,0),(-2,2,0), \dots ,$ (q(1), |q(1)|, 0) and then from (q(1), |q(1)|, 0) it goes through $(q(1),|q(1)|+1,-1),$ $(q(1),|q(1)|+2,-2), \dots , (q(1),|q(1)|+|q(3)|,q(3))=q$. It actually uses |q(1)| steps in a lane and then |q(3)| steps on another lane, together q(2) steps. The proof of the case is done.    $\square$

The next proposition can be proven with a similar technique.

Proposition 2

Let q(q(1), q(2), q(3)) be an odd pixel such that $|q(2)|\ge |q(1)|$ and $|q(2)|\ge |q(3)|$.

• If $q(2)>0$, then a shortest path from (0, 0, 0) to q is obtained as the concatenation of 1 $\downarrow _1$ step, $-q(1)$ $\swarrow _2$ steps and $-q(3)$ $\searrow _2$ steps: $\downarrow _1 \swarrow _2^{|q(1)|} \searrow _2^{|q(3)|}$.

• If $q(2)<0$, then a shortest path from (0, 0, 0) to q is obtained as the concatenation of 1 $\uparrow _3$ step, $q(3)-1$ $\nwarrow _2$ steps and $q(1)-1$ $\nearrow _2$ steps: $\uparrow _3 \nwarrow _2^{|q(3)-1|} \nearrow _2^{|q(1)-1|}$.

Observe that in the obtained paths the largest coordinate difference (the second coordinate in our case) is decreased in every step. Consequently, the (digital) distance of any two pixels can be computed as:

Lemma 1

$$ d(p(p(1),p(2),p(3)),q(q(1),q(2),q(3))) =\max _{i\in \{1,2,3\}}\{|p(i)-q(i)|\}.$$

We note here, that this result can be seen as a special case of one of the main results of [12,13,14], but here we have used a much simpler formulation. (Instead of allowing neighborhood sequences to generate distance functions, in our case, in each step we could step to any neighbors of the actual pixel. This allows us to derive the simple formula established in the previous lemma.)

In this paper we concentrate on the shortest paths. Some of them can be generated by a greedy algorithm (related to the algorithm of [11]), since some steps of the algorithm may contain a non-deterministic choice. However, there could be some of them that cannot be generated by the greedy algorithm.

A shortest path in the triangular grid may contain various steps. Notice that some of the vectors (representing elements of $\varSigma$) can be used to any pixels (zero-sum vectors). Some vectors can be applied only for even pixels (vectors with sum 1) and some of them can be applied only for odd pixels (vectors with sum $-1$). Thus, for instance the sequence of steps $\uparrow _1 \uparrow _3$ can be applied for odd pixels only, while the sequence $\uparrow _3 \uparrow _1$ works only starting from an even pixel. The order of the steps becomes important, because the triangular grid is not a lattice, and thus, some of the grid-vectors do not translate the grid to itself.

4 Generalized Traces Describing Shortest Paths

In this section we present an associative calculus that provides all the shortest paths equivalent to the one the process starts with. First, we recall the definition: $\mathcal C = (\varSigma , P)$ is an associative calculus, where $\varSigma$ is a finite alphabet and P is a finite set of productions (rewriting rules). Each rewriting rule is an element of $\varSigma ^* \times \varSigma ^*$. A rule is usually written in the form $u \leftrightharpoons v$, where $u,v\in \varSigma ^*$. Let $w\in \varSigma ^*$ be given, we say that $w'$ is obtained from w applying the rewriting rule $u \leftrightharpoons v$, if there exist $w_1,w_2\in \varSigma ^*$ such that either $w=w_1 u w_2$ and $w'=w_1 v w_2$, or $w=w_1 v w_2$ and $w'= w_2 u w_2$. Actually, w can also be obtained from $w'$ by the same production, thus we may use the notation $w \Leftrightarrow w'$. By the reflexive and transitive closure of $\Leftrightarrow$, the relation $\Leftrightarrow ^*$ is defined.

Observe that the calculus $\mathcal C$ defines an equivalence relation on $\varSigma ^*$. The equivalence class represented by w is denoted by $\mathcal C(w) = \{w'~|~ w \Leftrightarrow ^* w'\}$.

Now, let us see how such a calculus can be applied to describe shortest paths. In any shortest path the largest coordinate difference of the two endpoints (that is the second coordinate value in our case) must decrease in each step.

Observe that the cardinality of $\varSigma$ is 18, but every pixel has only 12 neighbors. The triangular grid is not a lattice, the steps $\varSigma _\bigtriangleup = \{ \downarrow _1, \nwarrow _1, \nearrow _1, \leftarrow _2,\rightarrow _2, \nwarrow _2, \searrow _2, \nearrow _2, \swarrow _2, \uparrow _3, \searrow _3, \swarrow _3 \}$ can be used at even, and the steps $\varSigma _\bigtriangledown = \{ \uparrow _1, \searrow _1, \swarrow _1, \leftarrow _2,\rightarrow _2, \nwarrow _2, \searrow _2, \nearrow _2, \swarrow _2, \downarrow _3, \nwarrow _3, \nearrow _3 \}$ can be used at odd pixels. As one may observe, only the steps to 2-neighbor pixels can be applied for every pixel, the possible directions of steps to 1- and 3-neighbors depend on the parity of the actual pixel. The independence relation contains pairs of letters such that at least one of the letters indicates a step to a 2-neighbor pixel. In terms of traces, this fact can be concluded in the following way:

Lemma 2

In any paths, any letter $a\in \varSigma _\bigtriangleup \cap \varSigma _\bigtriangledown = \{ \leftarrow _2,\rightarrow _2, \nwarrow _2, \searrow _2, \nearrow _2, \swarrow _2 \}$ commutes with any letter $b\in \varSigma$ ($a\ne b$).

Moreover, in the triangular grid there are composite steps that can be broken to two steps in various ways. That is related to the serializations in generalized traces [7]. In the next lemma all of them are listed that are needed in shortest paths in the analyzed part of the grid, i.e., the second coordinate is modified by two (during these steps). For the other parts of the grid the description is analogous.

Lemma 3

The following equivalences hold:

• $\nearrow _2 \nearrow _2$ is equivalent to $\uparrow _3 \nearrow _3$ for even pixels;

• $\nearrow _2 \nearrow _2$ is equivalent to $\nearrow _3 \uparrow _3$ for odd pixels;

• $\nwarrow _2 \nwarrow _2$ is equivalent to $\uparrow _3 \nwarrow _3$ for even pixels;

• $\nwarrow _2 \nwarrow _2$ is equivalent to $\nwarrow _3 \uparrow _3$ for odd pixels;

• $\nearrow _2 \nwarrow _2$ is equivalent to $\uparrow _3 \uparrow _1$ for even pixels;

• $\nearrow _2 \nwarrow _2$ is equivalent to $\uparrow _1 \uparrow _3$ for odd pixels;

• $\searrow _2 \searrow _2$ is equivalent to $\searrow _3 \downarrow _3$ for even pixels;

• $\searrow _2 \searrow _2$ is equivalent to $\downarrow _3 \searrow _3$ for odd pixels;

• $\swarrow _2 \swarrow _2$ is equivalent to $\swarrow _3 \downarrow _3$ for even pixels;

• $\swarrow _2 \swarrow _2$ is equivalent to $\downarrow _3 \swarrow _3$ for odd pixels;

• $\searrow _2 \swarrow _2$ is equivalent to $\downarrow _1 \downarrow _3$ for even pixels;

• $\searrow _2 \swarrow _2$ is equivalent to $\downarrow _3 \downarrow _1$ for odd pixels;

• $\downarrow _1 \searrow _2$ is equivalent to $\searrow _3 \swarrow _2$ for even pixels;

• $\downarrow _1 \swarrow _2$ is equivalent to $\swarrow _3 \searrow _2$ for even pixels.

Proof

We show the formal proof of the first equivalences. The others can be proven in a similar manner.

$$\begin{aligned} \nearrow _2 \nearrow _2 \text { is equivalent to } \uparrow _3 \nearrow _3 \text { for even pixels}. \end{aligned}$$

On the left side there are two consecutive steps to 2-neighbors, they are defined for all pixels. On the right side the first step is $\uparrow _3$ that is available only at even pixels, thus the statement has meaning only for even pixels.

Now, let us see the coordinate representations of these steps:

on the left side: $2(1,-1,0) = (2,-2,0)$, while

on the right side: $(1,-1,1)+(1,-1,-1)=(2,-2,0)$. The equivalence is established.    $\square$

It can be proven, e.g., by a combinatorial way, that there are no more equivalences of two consecutive steps (in our shortest paths) needed. The equivalences that are not listed in the previous lemmas, e.g., $\nwarrow _2 \nearrow _2$ is equivalent to $\uparrow _1 \uparrow _3$ for odd pixels, can be obtained by using some of the listed equivalences, e.g., $\nwarrow _2 \nearrow _2$ is equivalent to $\nearrow _2 \nwarrow _2$ (by Lemma 2) and that is equivalent to $\uparrow _1 \uparrow _3$ for odd pixels (by Lemma 3). Of course, there are longer sequences of steps that are equivalent to each other, e.g., $\downarrow _1 \downarrow _3\swarrow _3 \swarrow _2$ is equivalent to $\swarrow _2 \swarrow _2 \swarrow _2 \downarrow _1$, but their equivalence is based on the listed equivalences by two consecutive steps. It can be proven that the equivalence of every (consecutive) sequence of steps (in our shortest paths) to another sequence is based on the listed equivalences.

Based on the previous lemmas we are ready to present a rewriting system (especially, an associative calculus) that can obtain all the shortest paths that are equivalent to an initial one. Since the parity of the pixels plays an important role, in a path we keep track of them by allowing it to write this information after any step to a 2-neighbor pixel, e.g., the shortest path $\nearrow _2 \uparrow _3 \nearrow _2 \nearrow _2 \nwarrow _2$ to the pixel $(4,-5,2)$ can also be written in the following forms: $\nearrow _2 (e) \uparrow _3 \nearrow _2 \nearrow _2 (o) \nwarrow _2$ or $\nearrow _2 (e) \uparrow _3 \nearrow _2 (o) \nearrow _2 (o) \nwarrow _2 (o)$, etc. The latter form when all the steps to 2-neighbors are extended with this information is called fully informed description of the path. For steps to 1-neighbor or 3-neighbor pixels we do not need additional information, since not the same steps are allowed for even and for odd pixels, i.e., $\varSigma _\bigtriangleup \cap \varSigma _\bigtriangledown$ does not contain any steps to a 1- or a 3-neighbor pixel. In the following theorem this extended form is used (however, one may get any correct forms by deleting any/all these information). The theorem is a consequence of the previous results, especially of Lemmas 2 and 3.

Theorem 2

Let $\mathcal C(\varSigma ,P)$ be an associative calculus with rewriting rules

Let $\mathcal C(w)$ denote the set of all words that can be obtained from a given fully informed description of a word $w\in \varSigma ^*$ by applying any (finite number) of the rewriting rules of P.

Let $w\in \varSigma ^*$ be a fully informed description of a shortest path from (0, 0, 0) to a pixel q ($|q(2)|\ge |q(1)|$, $|q(2)|\ge |q(3)|$). Then, applying $\mathcal C$ to w, the set $\mathcal C(w)$ contains exactly those strings that describe shortest paths from (0, 0, 0) to q (by a fully informed description).

Actually, the system can be understood as a generalized trace [7] as we detail below. The system has several permutative rules, the rules by which a step to a 2-neighbor can be interchanged in the path with the previous or the next step (if it is not the same). However, the system has another types of productions, e.g., $\nwarrow _2(e)\nwarrow _2(e) \leftrightharpoons \uparrow _3\nwarrow _3$ or $\searrow _3\swarrow _2(o) \leftrightharpoons \downarrow _1\searrow _2(o)$. To have our system in a more similar fashion as the description in [7], we can introduce new letters abbreviating these “double steps”. In the mentioned examples they could be: $\nwarrow _{2+2} (e)$ and $\searrow _{1+2}$. These new letters show the unbroken “double step” referring the motion with vectors $(0,-2,2)$, and $(0,2,-1)$ in our case from even pixels (it is indicated in the first case, since this vector works for both even and odd pixels, while in the second case it is obviously working only for even pixels). By breaking the original productions to two parts using these intermediate “double steps”, we got the productions $\nwarrow _{2+2} (e) \leftrightharpoons \nwarrow _2(e) \nwarrow _2 (e)$, $\nwarrow _{2+2} (e) \leftrightharpoons \uparrow _3\nwarrow _3$ and $\searrow _{1+2} \leftrightharpoons \searrow _3\swarrow _2(o)$, $\searrow _{1+2} \leftrightharpoons \downarrow _1\searrow _2(o)$, respectively. In this form the system is a generalized trace, but only shortest paths without any “double steps” can be counted as real shortest paths.

5 The Number of Shortest Paths

In this section, by complementing the results of [4], we count the number of shortest paths by a combinatorial approach. As we have already seen, there are two cases by the sign of q(2), and also by the parity of pixel q. In each case we gave a shortest path in Propositions 1 and 2, and now, enumerations are provided to compute the number of shortest paths.

Let us start with the case when q is even.

5.1 The Case of Even Paths

In this case, the parity of p and q are the same, i.e., both of them are even. There is a shortest path containing only steps to 2-neighbor pixels (see Proposition 1). However, there can be some other shortest paths in which some of the steps to 2-neighbors are replaced based on some of the productions shown in Theorem 2.

First, let us analyze the case $q(2)<0$. By Proposition 1 we have a shortest path $\nwarrow _2^{|q(3)|} \nearrow _2^{|q(1)|}$. From this path, by the calculus $\mathcal C$ given in Theorem 2, one can obtain any shortest path $\varPi$. Observe that in the calculus, apart from the permutative rules (that changes only the order of two consecutive steps) there are three types of real rewriting rules that can be applied. Based on them, let us introduce the following notations (for a shortest path $\varPi$).

Notation 1

In case $q(2)<0$, the letters $\gamma ,\delta$ and $\varepsilon$ are defined as follows.

• Let $\gamma$ be the number of application of rewriting rules $\nearrow _2(e)\nwarrow _2(e) \rightarrow \uparrow _3\uparrow _1$ and $\nearrow _2(o)\nwarrow _2(o) \rightarrow \uparrow _1\uparrow _3$ (minus the number of their applications in reverse directions).

• Let $\delta$ be the number of applications of $\nwarrow _2(e)\nwarrow _2(e) \rightarrow \uparrow _3\nwarrow _3$ and $\nwarrow _2(o)\nwarrow _2(o) \rightarrow \nwarrow _3\uparrow _3$ (minus the number of their applications in reverse directions).

• Let $\varepsilon$ be the number of applications of $\nearrow _2(e)\nearrow _2(e) \rightarrow \uparrow _3\nearrow _3$ and $\nearrow _2(o)\nearrow _2(o) \rightarrow \nearrow _3\uparrow _3$ (minus the number of their applications in reverse directions).

Then $\varPi$ contains the following numbers of the following types of steps:

Moreover, the order of some steps, the ones that changes the parity, takes matter: these steps are alternating in the following way: starting by a step $\uparrow _3$ (if any), then one step from the set $\{\uparrow _1 , \nwarrow _3, \nearrow _3 \}$, then again a step $\uparrow _3$ (if any), etc. The steps $\nwarrow _2$ and $\nearrow _2$ can be anywhere in any order. Consequently, to compute the number of shortest paths, we have

$$\frac{(\gamma +\delta +\varepsilon )!}{\gamma !\ \delta !\ \varepsilon !} \times \left( {\begin{array}{c}|q(1)|+\gamma +2\delta \\ |q(1)| -\gamma -2\varepsilon \end{array}}\right) \times \left( {\begin{array}{c}|q(2)|\\ |q(3)|-\gamma -2\delta \end{array}}\right) $$

different ones for a fixed value of $\gamma ,\delta ,\varepsilon$, ($\gamma ,\delta ,\varepsilon \ge 0$, $\gamma +2\delta \le |q(3)|$, $\gamma +2\varepsilon \le |q(1)|$). This can be seen as follows: let the $\gamma +\delta +\varepsilon$ many $\uparrow _3$ steps are given. The first term $\frac{(\gamma +\delta +\varepsilon )!}{\gamma !\ \delta !\ \varepsilon !}$ refers for the possibility to arrange the appropriate number of $\uparrow _1 , \nwarrow _3, \nearrow _3$ steps to have an alternating order of parity changing steps, as it is requested. The second term $\left( {\begin{array}{c}|q(1)|+\gamma +2\delta \\ |q(1)| -\gamma -2\varepsilon \end{array}}\right)$ gives the number of possibilities to place the $\nearrow _2$ steps into the path. Finally, the third term, $\left( {\begin{array}{c}|q(2)|\\ |q(3)|-\gamma -2\delta \end{array}}\right)$ gives the number of ways the $\nwarrow _2$ steps can be put into the path.

Observe that for these pixels $|q(2)| = q(1) + q(3)$. Finally, using the possible values of $\gamma ,\delta$ and $\varepsilon$, we obtain the following theorem.

Theorem 3

Let q(q(1), q(2), q(3)) be a pixel of the triangular grid such that $q(1)+q(2)+q(3) = 0$ and $q(2)<0$. Then, the number of shortest paths from the origin (0, 0, 0) to q is given by

$$\sum _{\gamma =0}^{\min \{|q(1)| ,|q(3)|\}} \sum _{\delta =0}^{\left\lfloor \frac{|q(3)| -\gamma }{2}\right\rfloor } \sum _{\varepsilon =0}^{\left\lfloor \frac{|q(1)| -\gamma }{2}\right\rfloor } \frac{(\gamma +\delta +\varepsilon )! \left( {\begin{array}{c}|q(2)|\\ |q(3)| -\gamma -2 \delta \end{array}}\right) \left( {\begin{array}{c}|q(1)| +\gamma +2 \delta \\ |q(1)| -\gamma -2 \varepsilon \end{array}}\right) }{\gamma ! \ \delta ! \ \varepsilon !} . $$

The case when $q(2)>0$ is analogous (with steps to downward directions).

Notation 2

In case $q(2)>0$, let the $\gamma ,\delta$ and $\varepsilon$ be defined as follows.

• Let $\gamma$ be the number of application of $\searrow _2(e)\swarrow _2(e) \rightarrow \downarrow _1\downarrow _3$ and $\searrow _2(o)\swarrow _2(o) \rightarrow \downarrow _3\downarrow _1$ (minus the number of their applications in reverse directions).

• Let $\delta$ be the number of applications of $\swarrow _2(e)\swarrow _2(e) \rightarrow \swarrow _3\downarrow _3$ and $\swarrow _2(o)\swarrow _2(o) \rightarrow \downarrow _3\swarrow _3$ (minus the number of their applications in reverse directions).

• Let $\varepsilon$ be the number of applications of $\searrow _2(e)\searrow _2(e) \rightarrow \searrow _3\downarrow _3$ and $\searrow _2(o)\searrow _2(o) \rightarrow \downarrow _3\searrow _3$ (minus the number of their applications in reverse directions).

The only other difference (based on the possible rewriting) is that in this case the “alternation” of steps from the set $\{\downarrow _1, \swarrow _3, \searrow _3\}$ and $\downarrow _3$ starts with a step from the first set and finishes by a $\downarrow _3$ step. The number of possible paths is given by the following formula; and it can be proven by the application of multiplication and addition rules, in a similar manner as in the previous case.

Theorem 4

Let q(q(1), q(2), q(3)) be a pixel of the triangular grid such that $q(1)+q(2)+q(3) = 0$ and $q(2)>0$. Then, the number of shortest paths from the origin (0, 0, 0) to q is computed as

$$\sum _{\gamma =0}^{\min \{|q(1)| ,|q(3)|\}} \sum _{\delta =0}^{\left\lfloor \frac{|q(1)| -\gamma }{2}\right\rfloor } \sum _{\varepsilon =0}^{\left\lfloor \frac{|q(3)| -\gamma }{2}\right\rfloor } \frac{(\gamma +\delta +\varepsilon )! \left( {\begin{array}{c}|q(2)|\\ |q(1)| -\gamma -2 \delta \end{array}}\right) \left( {\begin{array}{c}|q(3)| +\gamma +2 \delta \\ |q(3)| -\gamma -2 \varepsilon \end{array}}\right) }{\gamma ! \ \delta ! \ \varepsilon !} .$$

5.2 The Case of Odd Paths

This case is also divided into two parts based on the sign of q(2). Let us start with $q(2)<0$. By Proposition 2 a shortest path to q is given as $\uparrow _3 \nwarrow _2^{|q(3)-1|} \nearrow _2^{|q(1)-1|}$. In these shortest paths, the three types of rewriting of Notation 1 can be applied that change the types of the steps (not only their order). Consequently, let us define and use $\gamma$, $\delta$ and $\varepsilon$ similarly as in the case of even paths for $q(2)<0$, see Notation 1. Then the numbers of various steps that a shortest path $\varPi$ contain (with a fixed value of $\gamma ,\delta$ and $\varepsilon )$ are as follows:

Here the alternating sequence of steps $\uparrow _3$ and steps from the set $\{\uparrow _1, \nwarrow _3, \nearrow _3\}$ starts and ends with an $\uparrow _3$ step. Consequently, the final formula for the number of shortest paths in this case is computed:

Theorem 5

Let q(q(1), q(2), q(3)) be a pixel of the triangular grid such that $q(1)+q(2)+q(3) = 1$ and $q(2)<0$. Then, the number of shortest paths from the origin (0, 0, 0) to q is

$$\sum _{\gamma =0}^{\min \{q(1)-1 ,q(3)-1 \}} \sum _{\delta =0}^{\left\lfloor \frac{q(3)-1 -\gamma }{2}\right\rfloor } \sum _{\varepsilon =0}^{\left\lfloor \frac{q(1)-1 -\gamma }{2}\right\rfloor } \frac{(\gamma +\delta +\varepsilon )! \left( {\begin{array}{c}|q(2)|\\ q(1)-1 -\gamma -2 \varepsilon \end{array}}\right) \left( {\begin{array}{c}q(3) +\gamma +2 \varepsilon \\ q(3)-1 -\gamma -2 \delta \end{array}}\right) }{\gamma ! \ \delta ! \ \varepsilon !} .$$

Note that in this case $q(1),q(3) \ge 1$ and $|q(2)| = q(1)+q(3) -1$.

Now, let us consider the last case: q is odd, $q(2)>0$ and $q(2)=|q(1)|+|q(3)|+1$. This case is the most complex, since the parity of the pixels must be changed during the path, and in this direction any of the elements of the set $\{\downarrow _1, \swarrow _3, \searrow _3\}$ can be applied for such reason. Therefore, actually, it is easier to break the set of the shortest paths $\mathcal C(w)$ – where w could be, e.g., from Proposition 2, $w= \downarrow _1 (\swarrow _2(o))^{|q(1)|} (\searrow _2(o))^{|q(3)|}$ – to three disjoint sets. In this way, we can compute the number of shortest paths when the first parity changing step is $\downarrow _1$, is $\swarrow _3$ and is $\searrow _3$, separately. We may use the calculus $\mathcal C$ keeping the first parity changing step (but maybe moving it by permutative steps interchanging its place with some steps to 2-neighbors) starting from the following words, respectively: $\downarrow _1 (\swarrow _2(o))^{|q(1)|} (\searrow _2(o))^{|q(3)|}$, $\swarrow _3 (\swarrow _2(o))^{|q(1)|-1} (\searrow _2(o))^{|q(3)|+1}$ and $\searrow _3 (\swarrow _2(o))^{|q(1)|+1} (\searrow _2(o))^{|q(3)|-1}$.

Defining $\gamma$, $\delta$ and $\varepsilon$ in the same way, as they were in the case of even paths with $q(2)>0$ (Notation 2), one can obtain the final result for this, most complex case.

Theorem 6

Let q(q(1), q(2), q(3)) be a pixel of the triangular grid such that $q(1)+q(2)+q(3) = 1$ and $q(2)>0$. Then, the number of shortest paths from the origin (0, 0, 0) to q is given by

6 Concluding Remarks

First, we summarize our main results in Fig. 3 showing the number of shortest paths (red color) for the indicated pixels. As we have seen instead of the binomial coefficients that are obtained on the hexagonal lattice, more complex formulae can be used to compute these values. These numbers can be considered, as a kind of generalizations of the binomial coefficients using the triangular grid, and actually, they are the cardinalities of the sets representing trajectories of the shortest paths on the triangular grid. As we have seen they are closely connected to generalized traces.

Fig. 3.

A part of the triangular grid with the number of shortest paths from the origin. (The region for which the formulae are directly provided is shown with yellow background, for the other pixels the values can be obtained by rotating the grid.) (Color figure online)

We note here that a related result, namely, the number of shortest paths is computed by using only 1-neighbors (closest neighbors) and at most 2-neighbors for the triangular grid in [4], in this way, we have completed the task started there.