Journal of Integer Sequences, Vol. 18 (2015), Article 15.1.3 |

Institut für Mathematik

Technische Universität Berlin

Straße des 17. Juni 136

D-10623 Berlin

Germany

**Abstract:**

This paper is about counting lattice paths. Examples are the paths
counted by Catalan, Motzkin or Schröder numbers. We identify
lattice paths with walks on some path-like graph. The entries of
the *n*th power of the adjacency matrix are the number of paths of
length *n* with prescribed start and end position. The adjacency
matrices turn out to be Toeplitz matrices. Explicit expressions for
eigenvalues and eigenvectors of these matrices are known. This
yields expressions for the numbers of paths in the form of
trigonometric sums. We give many examples of known sequences that
have such expressions.

We also deal with cases where no explicit expressions for eigenvalues and eigenvectors of the relevant matrices are known. In some of these cases it is possible to use the characteristic polynomial to get linear recurrence relations for the numbers in question.

(Concerned with sequences A000129 A001519 A005207 A006012 A024175 A024537 A080937 A094286 A094287 A094288 A124302 A147748.)

Received August 6 2014;
revised versions received December 3 2014; December 23 2014.
Published in *Journal of Integer Sequences*, December 26 2014.

Return to