Motzkin numbers and related sequences modulo powers of 2

DOI10.1016/J.EJC.2018.05.004zbMATH Open1398.11046arXiv1608.05657OpenAlexW2962940499MaRDI QIDQ1663803FDOQ1663803

T. W. Müller, C. Krattenthaler

Publication date: 24 August 2018

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: We show that the generating function $su{m}_{nge0}{M}_n,z^n$ for Motzkin numbers $M_n$, when coefficients are reduced modulo a given power of $2$, can be expressed as a polynomial in the basic series $su{m}_{ege0}^{}{z}^{4^e}/(1-z^{2cdot{4}^e})$ with coefficients being Laurent polynomials in $z$ and $1-z$. We use this result to determine $M_n$ 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'eorie 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 coefficients, and for the sequence of hex tree numbers.

Full work available at URL: https://arxiv.org/abs/1608.05657

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Factorials, binomial coefficients, combinatorial functions (05A10) Combinatorial identities, bijective combinatorics (05A19) Binomial coefficients; factorials; (q)-identities (11B65)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Congruences for Catalan and Motzkin numbers and related sequences
• Automatic congruences for diagonals of rational functions
• A method for determining the mod-\(2^k\) behaviour of recursive sequences, with applications to subgroup counting
• Catalan and Motzkin numbers modulo 4 and 8
• Equivalence of the two-dimensional directed animal problem to a one- dimensional path problem
• Combinatorial resolution of systems of differential equations. III: A special class of differentially algebraic series

Cited In (2)

• Congruence properties of combinatorial sequences via walnut and the Rowland-Yassawi-Zeilberger automaton
• Modularity of generating series of winding numbers

This page was built for publication: Motzkin numbers and related sequences modulo powers of 2

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1663803)