The research and progress of the enumeration of lattice paths

Abstract

The enumeration of lattice paths is an important counting model in enumerative combinatorics. Because it can provide powerful methods and technical support in the study of discrete structural objects in different disciplines, it has attracted much attention and is a hot research field. In this paper, we summarize two kinds of the lattice path counting models that are single lattice paths and family of nonintersecting lattice paths and their applications in terms of the change of dimensions, steps, constrained conditions, the positions of starting and end points, and so on. (1) The progress of classical lattice path such as Dyck lattice is introduced. (2) A method to study the enumeration of lattice paths problem by generating function is introduced. (3) Some methods of studying the enumeration of lattice paths problem by matrix are introduced. (4) The family of lattice paths problem and some counting methods are introduced. (5) Some applications of family of lattice paths in symmetric function theory are introduced, and a related open problem is proposed.

Graphical abstract

Keywords

Enumeration of lattice paths / generating function / matrix / family of lattice paths / symmetric function

1 Introduction

Enumeration of lattice path is one of the important combinatorial counting models. Its appeal is that in the small scale, lattice paths look like a mathematical doodle, but when the scale of the problem of enumeration of lattice path is relatively large, it becomes complex and difficult [61]. On the one hand, lattice path counting can provide a powerful method and technical support in the study of discrete structures involved in chemistry, physics, probability theory and computer science. On the other hand, lattice path counting has many unproven and undiscovered properties, so it has always attracted much attention and is still a very active and hot research field.

The aim of enumeration of lattice path is to study how to find the number of paths in the integer lattice of specified dimension, from the starting point to the end point, under the selected set of steps and restrictions [44]. It is mainly affected by the following four factors: (1) dimension; (2) step sets; (3) restriction (constraint) conditions; (4) the position and the number of the starting point and the ending point.

The research of the model of the enumeration of lattice path starts from “ballot problem”, “Duchon's club model” and “gambler's ruin problem” [61]. Since then, lattice path model has been applied and permeated into different fields of mathematics. Maps, graphs, trees, permutations, lattice polygons, Young tableaux, continued fractions, integer partition, queues, etc., can be expressed in lattice paths ways. In computer science, the stacks, trees, permutation and combination [4], random walk and queuing theory in probability theory, model of certain polymers in chemistry, and the analysis polymeric structures in quantum mechanics and statistical mechanics can all be studied by lattice path counting model. Catalan number, Motzkin number, Schröder number, i.e., are the result of the numbers of the enumeration of lattice path.

For different step sets, destination end points, restriction conditions, restriction areas (such as the whole plane, right half plane [44], first quadrant [8,11,46], ribbon [15], wedge [47], cone [2,22], etc.), since the self-avoiding walk [2,22,47,61], space dimension [7,9,33,41], exact formula, asymptotic expression [10,54] count on many aspects, such as lattice path model is studied. The generating function [5], complex analysis [13], analytical combinatorial mathematics such as probability analysis method [1,18,20,23,33,38,66], transfer matrix [58], counting matrix [6], permanent [6,11], immanant [46], Pfaffian [32,36], tree [61], group represented by algebra combination methods [4,46,62]. The asymptotic and exact counting formulas or conjectures of many lattice path counting models are obtained by means of computational software and mathematical experiments. In this paper, we mainly review the existing results on two types of lattice path counting problems in two-dimensional Euclidean space integer lattice, where the starting point is the coordinate origin, the end point is any point in the first quadrant, and the steps are horizontal and vertical steps, oblique upward or downward, respectively. (1) The family of lattice path satisfying certain constraints when the starting point and the destination point are uniquely determined. (2) The starting point and destination point are not uniquely determined, but are multiple disjoint lattice path family that vary in a specified set.

This paper is arranged as follows. Section 2 introduces the preliminary conceptions of lattice path counting and related research progress, and lists several classic lattice path counting, such as simple steps and non-simple steps. In Section 3, the lattice path counting problem is studied by generating functions. In Section 4, the lattice path counting problem is studied by matrices. Section 5 discusses the counting problem of lattice path family. For the counting problem of disjoint lattice path family, the counting method is determined by permanent and determinant of the counting matrix, Pfaffian formula and immanant in two cases: the starting point and the destination point are certain and uncertain. Section 6 discusses the application of the disjoint lattice path family counting model to representation theory, and state a related open problem.

2 The preliminary conceptions and some examples

2.1 Some conceptions and its examples

Definition 2.1　In a coordinate system, a line parallel to a specified direction (such as a coordinate axis) and passing through an integer point on the coordinate axis is called a lattice line, and any point where the intersection of two lattice lines is an integer coordinate (that is, each coordinate is an integer) is called a lattice point.

Definition 2.2　A lattice path is a line that starts from a lattice point and moves along a lattice line to a specified lattice point. For the sequence of P=\{P_0,P_1,\cdots , P_k\} where P_i\in {\mathbb{Z}}^2 for i=1,\cdots ,k, consist a lattice path, P_0 is starting point, P_k is destination point. The vectors (\overrightarrow{P_0{P}_1},\overrightarrow{P_1{P}_2},\cdots ,\overrightarrow{P_{k-1}{P}_k}) are called steps, and the set of steps is called a step set, k is the number of steps in a lattice path, we call size or length of the lattice path. A step where the components of the coordinate have absolute values of 1 or 0 (not all 0) is called a simple step, otherwise it is called a non-simple step. We use “rook”, “knight”, “bishop” and “queen” in chess to distinguish different situations of non-simple steps.

In the first quadrant (including coordinate axis), from the start at (a,b ) to the destination point (n,m ) with step sets \{(1 ,0), (0,1 )\} of the lattice paths have (\genfrac{}{}{0ex}{}{n-a+m-b}{n-a}). In particular, the lattice path from the point (0,0) to the point (n,n), located above the x-axis and below the line y=x, the famous Dyck lattice path, which number is the first nth Catalan number C_n=\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n}). In general, C(n,m) is denoted for the number of lattice paths from the beginning (0,0 ) to the end (n,m).

In the first quadrant, the number of lattice paths from the start at (0,0 ) to the destination point (n,m), step sets \{(1 ,0), (0,1 ),(1,1)\} is Delannoy [3] which denoted by D(n,m ),

D(n, m)= \sum _{d=0}^{min\{n,m\}}(\genfrac{}{}{0ex}{}{m}{d})(\genfrac{}{}{0ex}{}{n+m-d}{m}).

In particular, when the restricted areas is above x axis and under the lines y=x (including the boundaries), the starting point is (0,0), the destination point is (n,n), the number of the lattice paths is the n\mathrm{t}\mathrm{h} large Schröder number S_n (Tab.1), that is

S_n= \sum _{k=0}^n\frac{1}{k+1}(\genfrac{}{}{0ex}{}{2k}{k})(\genfrac{}{}{0ex}{}{n+k}{2k}).

If we take symmetry transformation along the line y=x, scale increase to \sqrt{2}, and the coordinate system counterclockwise {45}^{\circ }, large Schröder lattice path, the corresponding set to \{( 1,1) ,(1, -1),(2, 0)\}, starting point (0,0) is not changed, the destination (n,n) transforms to (2n,0), restricted areas for x axis above and linear y=x under infinite triangle (including its boundaries). At this time from starting point (0,0) to the destination (2n,0) of the lattice path is n\mathrm{t}\mathrm{h} large Schröder number S_n. Catalan, its step set \{(1,1 ),(1,-1 )\}, starting point (0,0) is not changed, destination (n,n) transforms to (2n,0), restricted areas for x axis above and linear y=x under infinite triangle (including its boundaries). For odd number n, at this time from starting point (0,0) cannot reach point (n,0), namely the corresponding count number is 0. In order to discuss the convenience, we delete those 0. From the starting point (0,0) to the destination point (2n,0), the number of the lattice paths is the n\mathrm{t}\mathrm{h} Catalan numbers C_n. Thus, we call n be the half length of the lattice path.

Let step set be \{(1,0 ),(1,1),(1 ,-1)\}. Then the number of lattice path from start point (0,0) to destination point (n,0 ) in the first quadrant (include x axis) is the n \mathrm{t}\mathrm{h} Motzkin numbers M_n, its formula is

M_n= \sum _{k=0}^{\lfloor \frac{n}{2}\rfloor } (\genfrac{}{}{0ex}{}{n}{2k}) C_k,

where C_k is k \mathrm{t}\mathrm{h} Catalan number.

Tab.2 gives the first few terms of lattice paths of Catalan, Motzkin and large Schroder in the infinite triangle.

Narayana number [62] N(n, k) is the number of the lattice paths, which start point (0,0) to destination (2n,0), its step set be \{(1,1 ),(1,-1 )\}, restricted areas compose x axis above and linear y=x under infinite triangle (including its boundaries), has k peaks (the adjacent step of (1,1)(1,- 1) is called a peak). There are N(n,1) +N(n ,2)+ \cdots +N( n,n) =C_n.

Lukasiewicz path is a typical non-simple step, its step set is \{(1 ,-1),(1 ,0), (1,1 ),(1,2),(1 ,3), \cdots \}, restricted area is composed by x axis not below (i.e., in the first quadrant and x axis). Consider the number of lattice paths from (0,0) to (n,0 ). knight's step set is \{( 2,3) ,(3, 2)\}, restricted areas in the first quadrant, considering from (0,0) to (n,n ), lattice paths. The Lukasiewicz path model can convert trees into lattice paths [61].

In the counting problem of tree and forest objects in combinatorics, the most famous parking function related shuffle conjecture [60] is used in the description of Dyck lattice path (see Fig.1 in [60] for details). In addition, there are partially directed lattice path models such as partially directed path, directed tree, directed vesicles, and so on. The generating functions of lattice path counting sequences are closely related to statistical mechanics, for example: the limiting free energy can be studied through the radius of convergence of the generating function, and the quantity of the thermodynamic scaling property is related to the asymptotic property of the generating function [39]. By studying the directed lattice counting model in the wedge region enclosed by the y axis and a diagonal line, the thermodynamic properties of the corresponding polymer can be studied. Statistical mechanics studies the overall behavior of matter composed of a large number of particles. Entropy is a measure of the disorder of the system, and its definition includes the number of all possible microstates [47]. The generating functions for counting sequences of different microstates are an effective tool for studying lattice models of polymers. The parameters of the generating functions depend on energy. In combinatorial models, one focuses on the free energy density of each node or edge and its limit.

2.2 The advance of the related research topic

The periodicity of a lattice in Definition 1.1 stems from its translation invariance and can therefore be expressed by a recursive relation. In [28], the concept of graph lattice is introduced, which relates the graph to the lattice and the walk on the graph to the lattice path. The recurrence relation is a very convenient tool to study the lattice path counting problem, and it can be used to solve the two-dimensional lattice path counting problem related to the binary recurrence relation. Fig.1 shows that 4 kinds correspond to Catalan number C(h,k ), large Schröder number S(h,k), the lattice path of Motzkin number M(h,k) and the calculation process of the first seven terms. Their recurrence relations (where 0\le k\le h) and the corresponding initial conditions are shown in Tab.3.

We can extend the method in the case of simple steps to the case of non-simple steps. For example, the graph lattice proposed in [28], the transfer matrix method [58], the recurrence relation, and the count of random walk paths in the graph are used to study the lattice counting problem in the special case of non-simple steps. At present, there is no effective unified method for the general lattice counting problem of non-simple steps, and only some special cases can be studied. For example, in {\mathbb{Z}}^2, when the restricted region is the left of the line y=x-1 in the first quadrant, the step is like a rook, bishop, spider, and the starting point is the origin and the destination point is (n,n ), the generating function of the corresponding sequence of lattice counts is algebraic. And there can be an explicit expression [41,45]. The paper [40] studies the numbers of the paths from the point of view of recurrence relation for “rook” path counting. However, there is no result about the general endpoint [41]. Starting from {\mathbb{Z}}^2 [27], we study the lattice counting problem of “rook” and “queen”, and extend the problem to the general high dimensional case by means of an open problem, which needs to be studied.

There are also some other results on the lattice path counting problem. For Chung-Feller theorem of Dyck path, Ma and Yeh [49] were studied in depth, and several generalized forms of refinements were obtained. Eu et al. [29] gave Taylor expansions of several types of lattice path generating functions, and proved that the weighted free Schröder path also has Chung−Feller property. Guo [37] studied the extension of Chung−Feller theorem in the case of variable slope piecewise linear boundary pairs with k defects, consisting of a limited periodic moving path from the origin to (n,m ) lattice and a weak m ordered split of n. Yan [65] studied four simple steps of two-dimensional lattice counting formulas, and gave a bijective relationship between the number of lattice and m-defect lattice path. Lu [48] discussed the counting of k-chromatically inclined Dyck path. Du [26] improved two identities on (n,m)-Dyck path. Zhao [69] generalized Koroljuk formula [43] to the lattice path counting explicit formula.

Lattice path models were used in proving combinatorial identity, tree structure, permutation with forbidden pattern, partition and so on. For example, Stanley [59] listed 214 equivalent combinatorial structures to Dyck lattice. Chen team [19−21,38] has made great achievements in lattice paths counting, combinatorial proof of identities, and forbidden permutation. Deng [24] characterized permutations with forbidden patterns by canonical reduced decomposition, then by labelling and decomposing the corresponding lattice paths, he gave the bijections between them.

3 Using generating function study lattice path counting problem

Generating function establishes the bridge between discrete mathematics and continuous mathematics. It is one of the most effective tools to study lattice paths counting and has become a classical tool to solve discrete combinatorial mathematics problems [12]. The symbolic method [33] is used to directly transform the structured description of the lattice counting model into the functional equation or system of equations [25] satisfied by the generating function. When the functional equation can be solved and the generating function is relatively simple, the accurate counting formula can be obtained through the Taylor expansion of the generating function.

Example 3.1　Let W denotes from (0,0 ) to finish (2n, 0) Dyck path collection. Let’s talk about that by what’s called “First passage decomposition”[61]. The Dyck path is either 0 in length, that is, the beginning and end points are the same (denoted by the letter \epsilon), or not less than 2 in length. Length is equal to the 2 Dyck path, the first step must be (1,1), the second step is necessarily (1,-1). A Dyck path longer than 2 must contain points on the x axis except the starting point. Set x_0 is in addition to the starting point of the first x in the points on the axis, the following investigation from the starting point the way to x_0 start is (1,1) (expressed in U), the last step is to (1,1) (D) with the way, they are still Dyck path. This is what is called “First passage”. The subsequent path from X_0 to the destination (2n, 0) is still a Dyck path. So you get

W=\underset{\mathrm{e}\mathrm{m}\mathrm{p}\mathrm{t}\mathrm{y}\mathrm{p}\mathrm{a}\mathrm{t}\mathrm{h}}{\underbrace{\epsilon }}\bigcup \underset{\mathrm{F}\mathrm{i}\mathrm{r}\mathrm{s}\mathrm{t}\mathrm{p}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{a}\mathrm{g}\mathrm{e}}{\underbrace{U\times W_1\times D}}\times W_2,

where W_1 and W_2 are still Dyck path sets.

C(x)=1+ x^{2}C(x{)}^2.

The resulting generating function is C(x)= \frac{1-\sqrt{1-4x^2}}{2x^2}, which is the branch and arrive at the final solution.

By using the generalized Newton binomial theorem, we obtain its power series expansion (Taylor's expansion): C(x)={\sum }_{n=0}^{\mathrm{\infty }}\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})x^{2n}. For the half-length n, the generating function is

\sum _{n=0}^{\mathrm{\infty }}\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n}) x^n=\frac{1-\sqrt{1-4x}}{2x}=C(x).

For some special bivariate generating functions, the expansion of the inverse series can be obtained by combinatorial inversion.

Kernel method is an effective method [1,38,56] to obtain generating functions by solving functional equations. It originated from Exercise 2.2.1.4 in Donald E. Knuth's “The Art of Computer Programming” and was later independently rediscovered by many people and called Kernel method [56]. The algebraic expression of the ordinate of a step is called the step polynomial. If step set is \{(a_1,b_1), (a_2,b_2 ),\cdots \}, then step polynomial is P(x)=x^{b_1}+x^{b_2}+\cdots. For Example 3.2 below, its step set is \{(1,1 ),(1,-1 )\}, P(x)=x +\frac{1}{x}. According to step polynomial and iteration relation, the function equation of multivariate generating function can be obtained. For some variable associations, the denominator (numerator) is equal to zero. Since we know that the expansion of power series must exist, the numerator (denominator) must be equal to zero, and the equation corresponding to the denominator (numerator) being equal to zero is called the kernel equation [56]. For Example 3.2 Dyck lattice path, step on polynomial P(x), said K(z,x) =1-zP(x) for kernel, K(z,x)=0 for kernel equation.

Kernel method is based on recurrence relation and boundary value condition or initial value condition to obtain the function equation of multivariate generating function. According to the sense of the generating function, the denominator is equal to 0 for some association of variables (i.e., the so-called kernel equation is obtained from the step polynomial). Since the power series expansion is known to exist, the numerator must also be equal to 0. From this, the generating function for the special case can be obtained, and then the generating function for the general case can be obtained, as Example 3.2.

Example 3.2　For Dyck lattice path, its set is \{( 1,-1),( 1,1) \}. Natural number r,n satisfy conditions 0\le r\le n, from starting point (0,0) to (n,i ) restricted areas is the first quadrant (not below x axis) goes to a(n,i ). Let f_i(z) be the generating function of a(n,i) sequence of number of lattice paths which starting (0,0 ) to (n,I ). Let z,x be two variables, we denote {\sum }_{n\ge 0}a (n,i )z^n with f_i(z). By the recursive relations a(n,i) =a(n -1,i-1)+a(n -1,i+1) and boundary value conditions a(n,n) =1, we obtain:

\begin{array}{rl}& a(n,i)z^n=za(n-1,i-1)z^{n-1}+za(n-1,i+1)z^{n-1},\\ & \sum _{n\ge 0}a(n,i)z^n=z\sum _{n\ge 0}a(n-1,i-1)z^{n-1}+z\sum _{n\ge 0}a(n-1,i+1)z^{n-1},\\ & f_i(z)=z{f}_{i-1}(z)+z{f}_{i+1}(z),\\ & f_0(z)=1+f_1(z).\end{array}

For the generating function F(z,x) ={\sum }_{n\ge 0}{f}_n(z) x^n, we multiply both sides of the second last expression above by x^i and sum them, with the last expression, we obtain

F(z, x)=z xF(z ,x)+ \frac{z}{x}[F(z ,x)- F(z, 0)]+1.

There is

F(z, x)=\frac{zF(z,0)-x}{z{x}^2-x+z}.

Thus, the step polynomial is P(x):=\frac{1}{x}+x, kernel equation is 1-zP(x)=1- z(\frac{1}{x}+x)=0, namely z x^2-x+z=0. Solving it we obtain two roots as

x_1=\frac{1-\sqrt{1-4z^2}}{2z}, x_2=\frac{1+\sqrt{1-4z^2}}{2z}.

We call a root whose value also tends to 0 as z tends to 0 a small root. Here x_1 is a small root, namely when z,x\to 0, x-x_1\sim x-z. Since it is known that the generating function must exist, the numerator must be equal to 0, namely zF(z, 0)- x_1=0, there is

F(z,0) =\frac{1-\sqrt{1-4z^2}}{2z^2}.

This is exactly the generating function corresponding to Catalan number in Dyck path, that is, the conclusion in Example 3.1. By substituting this into the expression for F(z,x), the generating function in the general case can be obtained:

F(z,x) =\frac{1}{z(x-x_2)}={\displaystyle \frac{1}{z\left(x-{\displaystyle \frac{1+\sqrt{1-4z^2}}{2z}}\right)}}.

Hou [38] solved the binary linear recursive relation system by kernel method, and solved the counting problem with two permutation conditions simultaneously. It is difficult to solve general bivariate and multivariate generating function equations. For example, the generating function equation of knight path in [14] remains to be studied.

The paper [61] gave a hierarchical classification of generating functions:

\{\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\}\subset \{\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{e}\mathrm{b}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{c}\}\subset \{\mathrm{D}\text{-}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{e}/\mathrm{h}\mathrm{o}\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{c}\}.

Here are the definitions of these three types of functions:

Definition 3.3　A formal power series F(z) is rational if there exist polynomials P(z),Q (z), with Q(x)\ne 0, such that F(x)=\frac{P(x)}{Q(x)}.

Definition 3.4　A formal power series F(z) is algebraic if there exist polynomials P_0(0) ,P_1(x), \cdots ,P_d(x ), not all 0, such that

P_d(x)F(x{)}^d+P_{d-1}F( x{)}^{d-1}+\cdots +P_1( x)F(x) +P_0(x) =0.

The smallest positive integer d for which this equation holds is called the degree of F.

Definition 3.5　A formal power series F(z) is D-finite or holonomic, if there exist polynomials P_0(x),P_1(x),\cdots , P_d(x), with the property P_d(x)\ne 0, such that

P_d(x)F(x{)}^{(d)}+P_{d-1}F(x{)}^{(d-1)}+\cdots +P_1 (x)F(x {)}^{(1)}+P_0(x)=0,

where F(x{)}^{(m)} and m=d,d-1, \cdots ,1 is the order of the differential equation.

For the study of lattice counting in two-dimensional Euclidean space, the following results have been obtained.

Theorem 3.1 [14]　 Let S be a finite subset of {\mathbb{Z}}^2 that is symmetric with respect to the x-axis and has small height variations. Let (i_0,j_0)\in {\mathbb{N}}^2. Then the length generating function for walks that start from (i_0,j_0), take their steps in S and stay in the first quadrant is D-finite.

Theorem 3.2 [14]　 The length generating function for walks that start from (1,1), take their steps in \{(- 1,2) ,(2, -1)\} and always stay in the first quadrant (knight walks) is not D-finite. Nor is the generating function for knight walks that end on the x-axis.

Bousquet-Mélou [13,14] have also studied other types of knight and shown that their generating functions are D-finite, the explicit expressions for generating functions and counting sequences cannot be obtained. By means of an affine transformation [61], we first transform the lattice path counting problem under non-simple step set into a lattice path counting problem under simple step set, and then apply the transfer matrix method to get the counting formula. The partial results are shown in the sequence A277248 [30].

For the general case, in two papers [1,12], that have been shown that the counting generating functions for the 23 walks of 2^8 kinds with small steps confined in a quarter-plane and associated with a finite group of birational transformations are D-finite. The lattice model restricted in the first quadrant is fundamentally different in the case of 79 kinds, where 23 species are finite groups and 56 kinds are infinite groups. In paper [46], Riemannian surface, universal covering, meromorphic branches and other analytical methods are used to prove this classification. Zhang [68] gave five mock theta functions by using the Bailey pair. Identities are established between the double sums and classical mock theta functions. Bostan [10] proposed an experimental mathematics approach leading to the computer-driven discovery of various conjectures about structural properties of generating functions coming from enumeration of restricted lattice walks in 2D and in 3D. Various conjectures are given from the structural properties of their algebraic equations, differential equations and asymptotic formulas. See Tab.1-Tab.3 in Appendix of [10] for details. Recently Bousquet-Mélou [11] has given an elementary constructive proof of the proposition that the generating functions of Gessel models are algebraic functions. Though 23 of these kinds of situations have been proved to be correct [53,41,54], but the others are open problems.

4 Using matrix study lattice path counting problem

It is an important method in algebraic combinatorics to study the lattice path counting problem by means of matrix and its determinant, permernent, Pfaffian, immanant, etc. There are many good results.

Definition 4.1　Let a=(a_1,a_2,\cdots ,a_n), b=(b_1,b_2,\cdots ,b_n) be integer number sequences, which satisfy that a_1\le a_2\le \cdots \le a_n, b_1\le b_2\le \cdots \le b_n and b_i\le a_i, i=1,2,\cdots ,n. We call n\times n matrix {\left((\genfrac{}{}{0ex}{}{a_i-b_j+1}{j-i+1})\right)}_{1\le i,j\le n} as counting matrix.

Theorem 4.1 [44]　 In the lattice area enclosed by the lattice path \{(1, a_1)(2, a_2)\cdots (n ,a_n)\} (its ith ordinate of step is a_i) and the lattice path \{(1 ,b_1)(2 ,b_2)\cdots ( n,b_n)\} (its ith ordinate of step is b_i), for step (1,0) or (0,1), ith step (that is, through the lattice point (i,y)) ordinate satisfying b_i\le y\le a_i, the number of lattice paths from (0,b_1) to (n,a_n ) is equal to the determinant of the counting matrix

{\mathrm{d}\mathrm{e}\mathrm{t}}_{1\le i,j\le n}\left((\genfrac{}{}{0ex}{}{a_i-b_j+1}{j-i+1})\right).

Fig.2 shows the specified lattice path \{(1,2 )(2,2) (3,2 )(4,6) (5,6 )(6,6) \}, which length is n=6 in the area enclosed by two lattice paths \{(1, 3)(2,5)(3, 7)(4,8)(5, 8)(6,8)\} and \{(1 ,0)(2,1 )(3,1) (4,4 )(5,5) (6,5 )\}.

Another kind of lattice path counting problem can be solved by using Theorem 4.1 and Dummy path technique.

Theorem 4.2 [44]　 Suppose that C_1,C_2,\cdots , C_n are the points of divergence in {\mathbb{Z}}^2. Then the number of lattice paths from (a,b ) to (c,d) which do not go on the point C_1,C_2 ,\cdots ,C_n equal to

{\mathrm{d}\mathrm{e}\mathrm{t}}_{1\le i,j\le n+1}(|L(A_j\to E_i)|),

where |L(A_j \to E_i)| denotes the number of lattice paths from A_j to E_i. A_1=(a,b),A_2 =C_1, \cdots ,A_{n+1}=C_n,E_1 =(c, d),E_2=C_1,\cdots , E_{n+1}=C_n.

Example 4.1 [31]　For Dyck path, let a=(0,1 ,\cdots ,n), b=(0 ,0,\cdots , 0). According Theorem 4.1, we obtain the determinant representation of Catalan number as follows:

C_n={\mathrm{d}\mathrm{e}\mathrm{t}}_{1\le i,j\le n}((\genfrac{}{}{0ex}{}{a_i+1}{j-i+1}))= {\mathrm{d}\mathrm{e}\mathrm{t}}_{1\le i,j\le n}((\genfrac{}{}{0ex}{}{i}{j-i+1}) ).

Example 4.2 [55, (s,t)-Tennis Ball Problem]　At the first turn, there are s tennis balls marked 1,2,\cdots ,s. Player throw t (t\le s) of them onto the lawn. At the second turn, tennis balls marked s+1,s+2,\cdots ,2s are added, with the remaining s-t balls there are 2s-t tennis balls, he throws another t tennis balls onto the lawn. This goes on for n turns. How many possible scenarios are there for nt tennis balls on the lawn at the end?

Author in paper [55] has shown that case number is equal to the desires of from the origin to ((s -t)n,tn), step sets \{E=(1 ,0), N=(0 ,1)\}, between x-axis and boundary (N^t{E}^{s-t}{)}^n of the way.

a_i=\{\begin{array}{ll}t,& \mathrm{i}\mathrm{f}i=1,2,\cdots ,s-t;\\ 2t,& \mathrm{i}\mathrm{f}i=s-t+1,\cdots ,2(s-t);\\ ⋮& \\ nt,& \mathrm{i}\mathrm{f}i=(n-1)(s-t)+1,\cdots ,n(s-t).\end{array}

Thus, we obtain that {\mathrm{d}\mathrm{e}\mathrm{t}}_{1\le i,j\le (s-t)n}((\genfrac{}{}{0ex}{}{a_i+1}{j-i+1}) ).

5 Study the enumeration of families of lattice paths

The problem of enumeration of lattice paths from one starting point to one destination point is discussed above. From now we discuss the problem of counting the families of lattice paths from the starting point to the ending point when there are multiple starting points and multiple ending points.

It is necessary to understand the concept of compatible point in two families. In the {\mathbb{Z}}^2 lattice, two lattice points are listed: u=(u_1 ,u_2, \cdots ,u_r) and v=(v_1,v_2,\cdots , v_r). Here, r can be any positive integer, when , , if from u_i to v_l every lattice path must intersects with every paths from u_j to v_k, says u compatible with v, if any two points are vertices of graph G, we say u G-compatible with v.

5.1 Lattice path family counting problem with specified start and end points

Disjoint lattice path counting was first obtained by Lindström, later it was rediscovered by Gessel and Viennot [34,35] from the perspective of integer plane partition, and became a research hot spot. Disjoint path families appear in the form of vicious Walkers in statistical mechanics and Kekule structures in hexagonal ring diagrams in organic chemistry. Xu [64] proposed the concepts of complete forcing sets and complete forcing numbers of graphs, and obtained explicit formulas of hexagonal chain graphs. Zhang [67] studied the d-matching problem for a special class of 3-uniform hypergraphs.

Theorem 5.1 [6]　 Let G be a directed acyclic graph with n designated origin and destination nodes, and let H be the n\times n matrix, whose (i,j)-entry is the number of paths from the ith origin to the jth destination. The following statements hold:

(a) The number of n-paths is equal to the permanent of H.

(b) If G is nonpermutable, the number of nonintersecting n-paths is equal to the determinant of H.

Example 5.1 [6]　We define an n-path to be a collection of n paths from a set of n origins to a set of n destinations. To compute the number of 4-paths in our example, we first find the number of ways that each ant can reach each morsel. In the example these numbers can be computed easily using calculations similar to those that arise in Pascal’s triangle (see Fig.3(a)(b)(c)(d)(e)). We record the information in a square matrix H whose (i,j )-entry a_{ij} is the number of ways that Ant i can reach Morsel j.

Applying Theorem 5.1, one obtains a counting matrix H as follows:

H=\left(\begin{array}{cccc}14& 6& 1& 0\\ 20& 15& 6& 1\\ 15& 20& 15& 6\\ 6& 15& 20& 14\end{array}\right).

Then the number of 4 lattice path families from the starting point O_A,O_B,O_C and O_D to the ending point A,B,C,D is equal to the permernent of the matrix H, \mathrm{p}\mathrm{e}\mathrm{r}(H)=171361.

As shown in Fig.3, this is a compatible diagram. The number of 4-disjoint lattice path families from the starting point O_A,O_B ,O_C and O_D to the ending point A,B,C,D is equal to the determinant of the matrix H, \mathrm{d}\mathrm{e}\mathrm{t}(H)=889.

Using the counting method of disjoint lattice path families to evaluate the determinant of Hankel matrix has become a hot topic in recent years. In 2019, Wang [63] explored the problem of evaluating the determinant of Hankel matrix with the convolution power of Catalan number by finding shifted periodic continued fractions. The relevant research progress can also be referred to the references listed in [63].

5.2 Lattice path family counting problem with undetermined starting point or (and) end point

Consider the following cases: (1) the starting point is specified and the ending point is selected from a given set; (2) The starting point is selected from the given set, and the end point is specified; (3) The starting point and end point are selected from two sets respectively. In this case, the Pfaffian formula is used to count the disjoint lattice path families.

To give a Pfaffian definition, we first introduce perfect matching of sets [50]. Here is a simple example to illustrate: For collection A=\{1,2 ,3,4, 5,6\}, \pi =\{\{1,2 \},\{3, 5\}, \{4, 6\}\} is a perfect matching to A. The matching of A=\{ 1,2,3 ,4,5, 6\} can be realized geometrically by drawing points labelled 1,2,3,4,5,6 along a line, and then connecting any two points whose labels are paired in the matching by a curve, this is so-called Brauer diagram. Any two pairs i,k and j,l in a matching for which are called a crossing of the matching. The sign \mathrm{s}\mathrm{g}\mathrm{n} of a matching \pi is (-{)}^c, where c is the number of crossings of \pi. In Fig.4, c=1, \mathrm{s}\mathrm{g}\mathrm{n} \pi =-1.

In general, upper triangular matrix Pfaffian defined

\mathrm{P}\mathrm{f}(A)=\sum _{\pi \mathrm{i}\mathrm{s}\mathrm{a}\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{f}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{c}\mathrm{h}\mathrm{i}\mathrm{n}\mathrm{g}\mathrm{o}\mathrm{f}\{1,2,\cdots ,2n\}}\mathrm{s}\mathrm{g}\mathrm{n}\pi \prod _{\{i,j\}\in \pi }{a}_{ij}.

There is a formula about A, \mathrm{d}\mathrm{e}\mathrm{t}(A- A^{\mathrm{T}})=\mathrm{P}\mathrm{f}( A{)}^2.

Different from the case of Theorem 5.1, when the end of the disjoint lattice path family is not determined, Theorem 10.13.5 in [44] gives the relation between the generating function and Pfaffian formula.

Theorem 5.2 [44]　 Let G be a directed, acyclic graph with a weight function w on its edges. Let A=(A_1 ,A_2, \cdots ,A_{2n} ) and E=(E_1, E_2,\cdots ) be sequences of vertices in G. Then

where L_G(A_{\sigma }\to E| \mathrm{n}\mathrm{o}\mathrm{n}-\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{s}\mathrm{e}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{g}) is the set of all families ( P_1,P_2,\cdots ,P_{2n}) of non-intersecting paths, P_i connecting A_{\sigma (i)} with E_{k_i}, i=1,2,...,2n and , and Q_G(i, j;w) is the generating function \sum _{(P^{\prime },P^{″})}w(P^{\prime })w (P^{″}) for all pairs ( P^{\prime }, P^{″}) of non-intersecting lattice paths, where P^{\prime } connects A_i with some E_k and P^{″} connects A_j with some E_l, with .

For other cases, such as the number of lattice paths in the lattice path family is odd, and the starting point and (part of) ending point are not determined, you can refer to [44].

Pfaffian can be described as a signed weight generating function of a complete graph. The quotient ring of a Pfaffian polynomial ring of fixed size in a generic skem-symmetric matrix was studied in [36], that is, the Pfaffian ideal. Based on the number of turning points from north to east of disjoint lattice path, three determinant formulas are given to calculate the Hilbert series and Hilbert functions of Pfaffian rings and a closed multiplication formula for them. For Pfaffian numbers whose elements in lattice paths count matrix are combinatorial numbers, how to give its calculation formula remains to be studied. Carrozza and Tanasa [16] used the expression of Pfaffians as Grassmann integral to generalize a series of formulas relating generating function of paths in digraphs to Pfaffians. They derived the famous Lindström-Gessel-Viennot formula in the general case of a graph with cycle and extended Stembridge's conclusion. Feng [32] obtained an explicit expression of the number of perfect matching of 8.6.4 lattices with toroidal boundary by enumerating Pfaffians. However, the Kekule structures counting of the general lattice graph, especially the hexagonal multi-coronal graph of benzene hydrocarbons, remains to be studied.

6 Application of disjoint lattice path families counting model in symmetric function theory

Suppose that \lambda is a partition of the positive integer n, namely n={\lambda }_1+{\lambda }_2+\cdots +{\lambda }_r, where {\lambda }_1 \ge {\lambda }_2 \ge \cdots \ge {\lambda }_r>0, denoted as \lambda =({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_r). The squares in the Young tableaux of \lambda are filled with elements in \{1,2,\cdots ,n\}, and satisfy the relation of no decrease in rows and strict increase in columns. This is the form \lambda = ({\lambda }_1,\cdots ,{\lambda }_r), n-semistandard tableaux of shape \lambda = ({\lambda }_1,\cdots ,{\lambda }_r), T.

A variable sequence, X=(x_1, \cdots ,x_n), defined n-semistandard Young tableaux T rights expression of \omega (T)=\prod _{k=1}^n{x}_k^{\mathrm{♯}(T,k)}, the weight expression in Fig.5\omega (T) =x_1^4{x}_2{x}_3{x}_4{x}_5{x}_6. Through the weight expression, the Schur function is obtained. By means of this symmetric function, the lattice path counting model is related to the group representation theory. Definition based on partition s_{\lambda }( X)={\sum }_T\omega (T), in addition to

s_{\lambda } (X)=\frac{\mathrm{d}\mathrm{e}\mathrm{t}(x_i^{{\lambda }_j+n-j}{)}_{i,j=1}^n}{\mathrm{d}\mathrm{e}\mathrm{t}(x_i^{n-j}{)}_{i,j=1}^n},

and to express Schur function by completely homogeneous symmetric function. For more details, you can refer to [57].

Gessel and Viennot [34,35] through the following bijection in n- semistandard Young tableaux T correspondence between r lattice paths P=(P_1,\cdots ,P_r), which is a disjoint paths family [35,57]: The first i row element in T in turn as a convert from u_i=(-i,1), v_i=({\lambda }_i-i, n), i=1,2,\cdots ,r, the height of the level step of the path of P_i. Fig.5 shows the bijection between the three lattice path family and the 6-semistandard Young tableaux with shape \lambda =(4, 3,2) and the corresponding weight expression \omega (T)=x_1^4{x}_2 x_3{x}_4{x}_5 x_6.

Theorem 6.1 [57, Jacobi-Trudi determinant]　 Let the m-degree completely homogeneous symmetric function be h_m(X). Then

s_{\lambda } (X)=\mathrm{d}\mathrm{e}\mathrm{t}( h_{{\lambda }_j+j-i}(X){)}_{i,j=1}^r.

The content of group representation theory can be enriched by the study of finite group representation theory related to lattice path counting, such as Young diagram, Brauer diagram, Pfaffian, immanant and so on. For example, Macdonald polynomial [17,52], which is important in algebraic combinatorics, can connect the integrable models of geometry and mathematical physics and obtain the irreducible center representation fragments of the detailed decomposition in these two fields. In supersymmetric field theory in physics, Macdonald's function corresponds to the topological vertex graph, which is the structure of supersymmetric theory itself. See “Supersymmetric theory of special function (3) topology vertex with Macdonald’s function”. However, the general formula used at present is expressed by the monomial symmetric function rather than the Schur symmetric function. Since the irreducible properties are expressed by Schur symmetric functions, the Schur symmetric function expressions can explicitly describe the underlying structure of the representation, and their decomposition can be read directly from the corresponding Schur function expressions.

In the theory of representation, we study how to transform symmetric functions into expressions based on Schur functions, and study the positivity and combinatorial significance of their coefficients. Schur function is the most important basis in the ring of symmetric functions. There are many mathematical problems about the expansion of the Schur basis of symmetric functions. Of particular interest is obtaining combinatorial descriptions with positive coefficients in various expansions of the Schur basis, exemplified by the famous Littlewood-Richardson rule [51]. For ease of expression, we give the following definition.

Definition 6.1 [42]　A symmetric function is said to be Schur positive if it can be represented by nonnegative linear combinations of Schur functions.

Definition 6.2　For a matrix M=(M_{ij} ), whose elements are symmetric polynomials, M is said to be completely Schur positive if the determinant of each of its square submatrices is Schur positive.

Lauren Williams proposes an open problem.

Open Problem We already know that Jacobi-Trudi matrix is completely Schur positive. Can you find anything else like this matrix?

References

[1] Banderier C, Flajolet P. Basic analytic combinatorics of directed lattice paths. Theoret Comput Sci 2002; 281(1/2): 37–80

[2] BanderierCKrattenthaler CKrinikA, . Explicit formulas for enumeration of lattice paths: basketball and the kernel method. In: Lattice Path Combinatorics and Applications. Dev Math, Vol 58. Cham: Springer, 2019, 78–118

[3] Banderier C, Schwer S. Why Delannoy numbers?. J Statist Plann Inference 2005; 135(1): 40–54

[4] BanderierCWallner M. Local time for lattice paths and the associated limit laws. arXiv: 1805.09065

[5] Bell J P, Chen S S. Power series with coefficients from a finite set. J Combin Theory Ser A 2017; 151: 241–253

[6] Benjamin A T, Cameron N T. Counting on determinants. Amer Math Monthly 2005; 112(6): 481–492

[7] Bostan A, Bousquet-Mélou M, Kauers M. . On 3-dimensional lattice walks confined to the positive octant. Ann Comb 2016; 20(4): 661–704

[8] Bostan A, Chyzak F, van Hoeij M. . Hypergeometric expressions for generating functions of walks with small steps in the quarter plane. European J Combin 2017; 61: 242–275

[9] BostanAChyzak Fvan HoeijM, . Explicit formula for the generating series of diagonal 3D rook paths. Sém Lothar Combin, 2011/2012, 66: Art B66a (27 pp)

[10] BostanAKauers M. Automatic classification of restricted lattice walks. In: 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), DMTCS Proc, Vol AK. Nancy: Assoc Discrete Math Theor Comput Sci, 2009, 201–215

[11] Bousquet-Mélou M. An elementary solution of Gessel’s walks in the quadrant. Adv Math 2016; 303: 1171–1189

[12] Bousquet-MélouMMishnaM. Walks with small steps in the quarter plane. In: Algorithmic Probability and Combinatorics. Contemp Math, Vol 520. Providence: AMS, 2010, 1–39

[13] Bousquet-Mélou M, Petkovšek M. Linear recurrences with constant coefficients: the multivariate case. Discrete Math 2000; 225(1/2/3): 51–75

[14] Bousquet-Mélou M, Petkovšek M. Walks confined in a quadrant are not always D-finite. Theoretical Computer Science 2003; 307(2): 257–276

[15] Brak R, Essam J, Osborn J. . Lattice paths and the constant term. J Phys Conf Ser 2006; 42(1): 47–58

[16] Carrozza S, Tanasa A. Pfaffians and nonintersecting paths in graphs with cycles: Grassmann algebra methods. Adv in Appl Math 2018; 93: 108–120

[17] Chalykh O A. Macdonald polynomials and algebraic integrability. Adv Math 2002; 166(2): 193–259

[18] ChenS SChyzak FFengR Y, . On the existence of telescopers for mixed hypergeometric terms. J Symbolic Comput. 2015, 68: Part 1, 1–26

[19] Chen W Y C, Deng E Y P, Du R R X. Reduction of m-regular noncrossing partitions. European J Combin 2005; 26(2): 237–243

[20] Chen W Y C, Hou Q H, Zeilberger D. Automated discovery and proof of congruence theorems for partial sums of combinatorial sequences. J Difference Equ Appl 2016; 22(6): 780–788

[21] Chen W Y C, Li N Y, Shapiro L W, Yan S H F. Matrix identities on weighted partial Motzkin paths. European J Combin 2007; 28(4): 1196–1207

[22] Courtiel J, Melczer S, Mishna M. . Weighted lattice walks and universality classes. J Combin Theory Ser A 2017; 152: 255–302

[23] Deng L H, Deng Y P, Shaporo L W. The Riordan group and symmetric lattice paths. J Shandong Univ Nat Sci 2015; 50(4): 82–89, 94

[24] DengY P. Lattice paths and permutations with forbidden patterns. Ph D Thesis, Tianjin: Nankai Univ, 2004

[25] DrmotaM. Lecture on “Positive catalytic and non-catalytic polynomial systems of equations” Lattice Walks at the Interface of Algebra. Analysis and Combinatorics, BIRS, Banff, Sep 18–22, 2017

[26] Du R R X, Yu K. Refinements of two identities on (n,m)-Dyck paths. Adv in Appl Math 2018; 97: 54–63

[27] Erickson M, Fernando S, Tran K. Enumerating rook and queen paths. Bull Inst Combin Appl 2010; 60: 37–48

[28] Erusalimskiy I M. Graph lattice: random walk and combinatorial identities. Bol Soc Mat Mex (3) 2016; 22(2): 329–335

[29] Eu S-P, Fu T-S, Yeh Y-N. Refined Chung-Feller theorems for lattice paths. J Combin Theory Ser A 2005; 112(1): 143–162

[30] FengJ S. Sequence A277248. In: OEIS (On-Line Encyclopedia of Integer Sequences), 2016

[31] FengJ S. A Hessenberg determinant of Pascal’s triangle and Catalan numbers. 2020, arXiv: 1909.00611v2

[32] Feng X, Zhang L Z, Zhang M Z. Enumeration of perfect matchings of lattice graphs by Pfaffians. Appl Math Comput 2018; 338: 412–420

[33] FlajoletPSedgewick R. Analytic Combinatorics. Cambridge: Cambridge Univ Press, 2009

[34] Gessel I M, Viennot G. Binomial determinants, paths, and hook length formulae. Adv Math 1985; 58(3): 300–321

[35] GesselI MViennot G. Determinants, paths, and plane partitions. 1989

[36] GhorpadeS RKrattenthaler C. The Hilbert series of Pfaffian rings. In: Algebra, Arithmetic and Geometry with Applications (West Lafayette, IN, 2000), Berlin: Springer, 2004, 337–356

[37] Guo V J W, Wang X X. A Chung-Feller theorem for lattice paths with respect to cyclically shifting boundaries. J Algebraic Combin 2019; 50(2): 119–126

[38] Hou Q H, Mansour T. Kernel method and linear recurrence system. J Comput Appl Math 2008; 216(1): 227–242

[39] Janse van Rensburg E J, Ye L. Forces in square lattice directed paths in a wedge. J Phys A 2005; 38(40): 8493–8503

[40] Jin E Y, Nebel M E. A combinatorial proof of the recurrence for rook paths. Electron J Combin 2012; 19(1): Paper 59 (10 pp)

[41] Kauers M, Zeilberger D. The computational challenge of enumerating high-dimensional rook walks. Adv in Appl Math 2011; 47(4): 813–819

[42] King R C, Welsh T A, van Willigenburg S J. Schur positivity of skew Schur function differences and applications to ribbons and Schubert classes. J Algebraic Combin 2008; 28(1): 139–167

[43] Koroljuk V S. On the discrepancy of empiric distributions for the case of two independent samples. Izvestiya Akad Nauk SSSR Ser Mat 1955; 19: 81–96

[44] KrattenthalerC. Lattice path enumertation. In: Bóna M, ed. Handbook of Enumerative Combinatorics. Discrete Math Appl (Boca Raton). Boca Raton: CRC Press, 2015, 589–678

[45] Kung J P S, de Mier A. Catalan lattice paths with rook, bishop and spider steps. J Combin Theory Ser A 2013; 120(2): 379–389

[46] Kurkova I, Raschel K. On the functions counting walks with small steps in the quarter plane. Publ Math Inst Hautes Etudes Sci 2012; 116: 69–114

[47] LaferrièreD F. Classification of walks in wedges. M S Thesis. Burnaby: Simon Fraser Univ, 2007

[48] Lu Q L. Enumeration of k-colored skew Dyck path. J East China Normal Univ Nat Sci 2015; (3): 31–37

[49] Ma J, Yeh Y-N. Refinements of (n, m)-Dyck paths. European J Combin 2011; 32(1): 92–99

[50] Ma S M, Yeh Y-N. Eulerian polynomials, Stirling permutations of the second kind and perfect matchings. Electron J Combin 2017; 24(4): Paper No 4.27 (18 pp)

[51] MacdonaldI G. Symmetric Functions and Hall Polynomials. 2nd Ed. New York: Oxford Univ Press, 1995

[52] Macdonald I G. Orthogonal polynomials associated with root systems. Sém Lothar Combin 2000/2001; 45: Art B45a (40 pp)

[53] Melczer S, Mishna M. Asymptotic lattice path enumeration using diagonals. Algorithmica 2016; 75(4): 782–811

[54] MelczerSWilson M C. Asymptotics of lattice walks via analytic combinatorics in several variables. In: 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016), DMTCS Proc, Vol BC. Nancy: Assoc Discrete Math Theor Comput Sci, 2016, 863–874

[55] Merlini D, Sprugnoli R, Verri M C. The tennis ball problem. J Combin Theory Ser A 2002; 99(2): 307–344

[56] Prodinger H. Prodinger H. The kernel method: a collection of examples. Sém Lothar Combin 2003/2004; 50: Art B50f (19 pp)

[57] StanleyR P. Enumerative Combinatorics. Vol 2. Cambridge: Cambridge Univ Press, 1999

[58] StanleyR P. Enumerative Combinatorics. Vol 1. 2nd Ed. Cambridge: Cambridge Univ Press, 2012

[59] StanleyR P. Catalan Numbers. New York: Cambridge University Press, 2015

[60] Van Willigenburg S V. The shuffle conjecture. Bull Amer Math Soc (N S) 2020; 57(1): 77–89

[61] WallnerM. Combinatorics of lattice paths and tree-like structures. Ph D Thesis. Vienna: Vienna University of Technology, 2016

[62] Wang Y, Yang A L B. Total positivity of Narayana matrices. Discrete Math 2018; 341(5): 1264–1269

[63] Wang Y, Xin G C. Hankel determinants for convolution powers of Catalan numbers. Discrete Math 2019; 342(9): 2694–2716

[64] Xu S J, Zhang H P, Cai J Z. Complete forcing numbers of catacondensed hexagonal systems. J Comb Optim 2015; 29(4): 803–814

[65] Yan S H F, Zhang Y Q. On lattice paths with four types of steps. Graphs Combin 2015; 31(4): 1077–1084

[66] Yang S L, Dong Y N, Yang L, Yin J. Half of a Riordan array and restricted lattice paths. Linear Algebra Appl 2018; 537: 1–11

[67] Zhang Y, Lu M. d-matching in 3-uniform hypergraphs. Discrete Math 2018; 341(3): 748–758

[68] Zhang Z Z, Li X Q. Mock theta functions in terms of q-hypergeometric double sums. Int J Number Theory 2018; 14(6): 1715–1728

[69] Zhao J J Y. Koroljuk’s formula for counting lattice paths revisited. Util Math 2018; 107: 207–222

RIGHTS & PERMISSIONS

Higher Education Press 2022