We consider the Motzkin paths which are simple combinatorial objects appearing in many contexts. They are counted by the Motzkin numbers, related to the well known Catalan numbers. Associated with the Motzkin paths, we introduce the Motzkin polynomial, which is a multi-variable polynomial "counting" all Motzkin paths of a certain type. Motzkin polynomials (also called Jacobi-Rogers polynomials) have been studied before, but here we deduce some properties based on recurrence relations. The recurrence relations proved here also allow an efficient computation of the Motzkin polynomials. Finally, we show that the matrix entries of powers of an arbitrary tridiagonal matrix are essentially given by Motzkin polynomials, a property commonly known but usually stated without proof.
@article{10_37236_4781,
author = {Roy Oste and Joris Van der Jeugt},
title = {Motzkin paths, {Motzkin} polynomials and recurrence relations},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {2},
doi = {10.37236/4781},
zbl = {1310.05013},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4781/}
}
TY - JOUR
AU - Roy Oste
AU - Joris Van der Jeugt
TI - Motzkin paths, Motzkin polynomials and recurrence relations
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/4781/
DO - 10.37236/4781
ID - 10_37236_4781
ER -
%0 Journal Article
%A Roy Oste
%A Joris Van der Jeugt
%T Motzkin paths, Motzkin polynomials and recurrence relations
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/4781/
%R 10.37236/4781
%F 10_37236_4781
Roy Oste; Joris Van der Jeugt. Motzkin paths, Motzkin polynomials and recurrence relations. The electronic journal of combinatorics, Tome 22 (2015) no. 2. doi: 10.37236/4781
