Christian Krattenthaler and Thomas W. Müller

Motzkin numbers and related sequences modulo powers of 2

(28 pages)

Abstract. We show that the generating function Σn>=0Mnzn for Motzkin numbers Mn, when coefficients are reduced modulo a given power of 2, can be expressed as a polynomial in the basic series Σe>=0z4e/(1-z2.4e) with coefficients being Laurent polynomials in z and 1-z. We use this result to determine Mn modulo 8 in terms of the binary digits of n, thus improving, respectively complementing earlier results by Eu, Liu and Yeh [Europ. J. Combin. 29 (2008), 1449-1466] and by Rowland and Yassawi [J. Théorie Nombres Bordeaux 27 (2015), 245-288]. Analogous results are also shown to hold for related combinatorial sequences, namely for the Motzkin prefix numbers, Riordan numbers, central trinomial numbers, and for the sequence of hex tree numbers.

The following versions are available:

The paper is accompanied by the following Mathematica files: By using the notebook (which requires the other file as input file), you are able to redo (most of) the computations that are presented in this article.
Back to Christian Krattenthaler's home page.