Catalan and Motzkin numbers modulo 4 and 8
type: Item
instance of: scholarly article
title: Catalan and Motzkin numbers modulo 4 and 8
zbMATH Open document ID: 1149.11008
author: Sen-Peng Eu
author: Shu-Chung Liu
author: Yeong-Nan Yeh
published in: European Journal of Combinatorics
publication date: 2008-07-11T00:00:00Z
review text: \noindent Let \(C_n\) and \(M_n\) be the \(n\)th Catalan and Motzkin numbers, respectively. It is well-known and easy to prove that \(C_n\) is odd if and only if \(n+1\) is a power of \(2\). The values of \(n\) for which \(M_n\) is odd were classified by \textit{E.~Deutsch} and \textit{B. E. Sagan} [J. Number Theory 117, No. 1, 191--215 (2006; Zbl 1163.11310)]. This nice paper goes further and looks at Catalan and Motzkin numbers modulo \(4\) and \(8\). The Catalan numbers modulo \(8\) are classified in Theorem 4.2. For example, they are zero modulo 8 if the binary expansion of \(n+1\) has at least \(4\) bits. For values of \(n\) with \(n+1\) having at most three bits, \(C_n\) is not zero modulo \(8\). Further, \(C_n\) is never \(3\) modulo \(4\). The Motzkin numbers modulo \(8\) are classified in Theorem 5.5. As a byproduct of their results, the authors conclude that \(M_n\) is zero modulo \(4\) if and only if \(n+\delta=(4i+2\delta-1)4^{j+1}\) for some integers \(i\geq 0\), \(j\geq 0\), \(\delta\in \{1,2\}\), thus confirming a conjecture of Deutsch and Sagan. Furthermore, \(M_n\) is never zero modulo \(8\). The proofs use Kummer's theorem on the exponent of a prime dividing a binomial coefficient and Lucas' theorem giving the value of \({n\choose k}\) modulo a prime \(p\) in terms of the product of the binomial coefficients of the corresponding \(p\)-adic digits and involve a detailed analysis of the binary expansion of \(n\). For example, after finding \(C_n\) modulo \(8\) for all \(n\), the authors find \(M_n\) modulo \(8\) via the formula \[ M_n=\sum_{k\geq 0} {n\choose {2k}}C_k. \]
reviewed by: Florian Luca
Mathematics Subject Classification ID: 11B65
Mathematics Subject Classification ID: 11B83
zbMATH DE Number: 5300779
zbMATH Keywords: Catalan numbers
zbMATH Keywords: Motzkin numbers
zbMATH Keywords: binomial coefficients modulo 8
MaRDI profile type: Publication
full work available at URL: j.ejc.2007.06.019
OpenAlex ID: W2048492341
cites work: Prime and prime power divisibility of Catalan numbers
cites work: Lucas' theorem for prime powers
cites work: Q3358798
cites work: Congruences for Catalan and Motzkin numbers and related sequences
cites work: Motzkin numbers
cites work: On the Congruences of Some Combinatorial Numbers
cites work: Some congruences for Apery numbers
cites work: Pascal's triangle (mod 8)
cites work: On integrality and periodicity of the Motzkin numbers
cites work: Congruence properties of Apery numbers
cites work: Q4236280
cites work: Q3150942
DOI: 10.1016/J.EJC.2007.06.019
description: scientific article; zbMATH DE number 5300779