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

Lattice Path Enumeration and Toeplitz Matrices

Stefan Felsner and Daniel Heldt
Institut für Mathematik
Technische Universität Berlin
Straße des 17. Juni 136
D-10623 Berlin


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 nth 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.

Full version:  pdf,    dvi,    ps,    latex    

(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 Journal of Integer Sequences home page