Walks, Tilings, and Generating Functions

Several articles deal with tilings with various shapes, and also a very frequent type of combinatorics is to examine the walks on graphs or on grids. We combine these two things and give the numbers of the shortest walks crossing the tiled and square grids by covering them with squares and dominoes. We describe these numbers not only recursively, but also as rational polynomial linear combinations of Fibonacci numbers. 

We give many other recurrence relations for different types of self-avoiding walks. We investigate the number of the walks between two diagonally opposite corners in a finite rectangular subgraph of the integer lattice, subject to certain constraints. Furthermore, we research a new aspect of self-avoiding walks on graphs. We introduce the notion of wrong steps of self-avoiding walks on a rectangular shape n x m grid of square cells and examine some general and special cases.

We determine the number of self-avoiding walks with one and with two wrong steps in general, on n x 2 grids with arbitrary wrong steps, and in the only one kind of wrong steps case for arbitrary n x m grids.

Lattice path enumeration has been extensively studied in combinatorics, largely due to the wide variety of constraints that can be imposed on these discrete objects. By requiring that a path never visits the same vertex more than once, we obtain the well-known class of self-avoiding walks (SAWs). However, SAWs remain too difficult to  approach on their own, which motivates the study of restricted subclasses, such as walks confined to grid graphs or allowing only a fixed number of south and west steps (so-called “wrong steps” or “errors”).

In this setting, we study several families of SAWs starting at the origin and confined to the grid $\mathbb{N}\times\mathbb{N}$ using the symbolic method. We derive rational multivariate generating functions for SAWs with $w=0,1,2)$ errors, as well as for SAWs of height $h=1,2$, which yields closed formulas for their enumeration.

Finally, we study other statistics for these SAWs with a fixed number of errors, such as length, area under the curve, and number of corners. For this purpose, we use a generating function approach together with combinatorial arguments based on basic counting techniques and bijections for some of the obtained results.

Define the array $[m_{n,k}]_{n,k}$ for $n,k\in\mathbb{Z}$ as follows. Let $m_{k,n}=0$ unless $0\le k\le n$. In the latter case, $m_{0,0}=1$, and for $n\ge 1$ the elements $m_{n,k}$ satisfy

m_{n,k}=m_{n-1,k}+m_{n-1,k-1}+m_{n-1,k-2}.

The zero-free part of the array has a triangular shape structurally identical to Pascal's triangle, and it is called Motzkin triangle. The right diagonal leg of the triangle is the Motzkin sequence, which satisfies a second order linear recurrence with linear polynomial coefficients. We extend this relation to the parallel diagonals to the line of Motzkin sequence. In addition, we prove the existence of a recursive formula for the formation of three arbitrary elements in the triangle and construct the corresponding formulae for three connected entries. These recursive formulae have bivariate polynomial coefficients of higher order. Furthermore, we describe the columns of Motzkin triangle as polynomial values and reveal nice non-trivial factorization properties of these polynomials.

In combinatorics, generating functions are extremely useful objects for answering a wide range of questions about counting sequences associated with combinatorial classes. However, they are often very difficult to compute explicitly. For this reason, several strategies for determining generating functions have been developed. One such strategy involves Riordan arrays, which take advantage of the recursive nature of combinatorial classes to encode all the information of certain bivariate counting sequences using only two generating functions. Moreover, Riordan arrays have proven to be a powerful tool for studying various properties of these counting sequences.

In this talk, we will discuss several properties of the set of Riordan arrays and explore their algebraic structure. We will then apply this theory to families of lattice paths, such as lattice paths avoiding points of the form (2k+1,2k+1). Finally, we will present some open problems we are currently investigating, including asymptotic formulas, the existence of operators relating different families of lattice paths, and the characterization of lattice paths satisfying specific conditions.