Motzkin Paths, Motzkin Polynomials and Recurrence Relations

Abstract

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.