Geodesic
Lattice path enumeration and Toeplitz matrices
Journal of integer sequences, Tome 18 (2015) no. 1
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.
Classification : 05A15, 05A05, 15A09, 15B05
Keywords: Catalan number, Motzkin number, transfer matrix, trigonometric sum 
@article{JIS_2015__18_1_a2,
     author = {Felsner,  Stefan and Heldt,  Daniel},
     title = {Lattice path enumeration and {Toeplitz} matrices},
     journal = {Journal of integer sequences},
     year = {2015},
     volume = {18},
     number = {1},
     zbl = {1309.05020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2015__18_1_a2/}
}
TY  - JOUR
AU  - Felsner,  Stefan
AU  - Heldt,  Daniel
TI  - Lattice path enumeration and Toeplitz matrices
JO  - Journal of integer sequences
PY  - 2015
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/JIS_2015__18_1_a2/
LA  - en
ID  - JIS_2015__18_1_a2
ER  - 
%0 Journal Article
%A Felsner,  Stefan
%A Heldt,  Daniel
%T Lattice path enumeration and Toeplitz matrices
%J Journal of integer sequences
%D 2015
%V 18
%N 1
%U http://geodesic.mathdoc.fr/item/JIS_2015__18_1_a2/
%G en
%F JIS_2015__18_1_a2
Felsner,  Stefan; Heldt,  Daniel. Lattice path enumeration and Toeplitz matrices. Journal of integer sequences, Tome 18 (2015) no. 1. http://geodesic.mathdoc.fr/item/JIS_2015__18_1_a2/