×

Catalan and Motzkin numbers modulo 4 and 8. (English) Zbl 1149.11008

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 E. Deutsch and 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. \]

MSC:

11B65 Binomial coefficients; factorials; \(q\)-identities
11B83 Special sequences and polynomials

Citations:

Zbl 1163.11310
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alter, R.; Kubota, K., Prime and prime power divisibility of Catalan numbers, J. Combin. Theory Ser. A, 15, 243-256 (1973) · Zbl 0273.10010
[2] Davis, K. S.; Webb, W. A., Lucas’ theorem for prime powers, European J. Combin., 11, 229-233 (1990) · Zbl 0704.11002
[3] Davis, K. S.; Webb, W. A., Pascal’s triangle modulo 4, Fibonacci Quart., 29, 79-83 (1991) · Zbl 0732.11009
[4] Deutsch, E.; Sagan, B., Congruences for Catalan and Motzkin numbers and related sequences, J. Number Theory, 117, 191-215 (2006) · Zbl 1163.11310
[5] Donaghey, R.; Shapiro, L. W., Motzkin Numbers, J. Combin. Theory Ser. A, 23, 291-301 (1977) · Zbl 0417.05007
[6] Eu, S.-P.; Liu, S.-C.; Yeh, Y.-N., On the congruences of some combinatorial numbers, Stud. Appl. Math., 116, 135-144 (2006) · Zbl 1145.11303
[7] Gessel, I. M., Some congruences for Apery numbers, J. Number Theory, 14, 362-368 (1982) · Zbl 0482.10003
[8] Huard, J. G.; Spearman, B. K.; Williams, K. S., Pascal’s triangle modulo 4, European J. Combin., 19, 45-62 (1998) · Zbl 0889.11007
[9] Kummer, E. E., Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, J. Reine Angew. Math., 44, 93-146 (1852) · ERAM 044.1198cj
[10] Luca, F.; Klazar, M., On integrality and periodicity of the Motzkin numbers, Aequationes Math., 69, 68-75 (2005) · Zbl 1059.05005
[11] F. Lucas, Sur les congruences des numbres eulériens et des coefficients différentiels des fonctions trigonométriques suivant un modulo premier, Bull. Soc. Math. France 6 (1877-1878) 49-54; F. Lucas, Sur les congruences des numbres eulériens et des coefficients différentiels des fonctions trigonométriques suivant un modulo premier, Bull. Soc. Math. France 6 (1877-1878) 49-54
[12] Mimura, Y., Congruence properties of Apery numbers, J. Number Theory, 16, 138-146 (1983) · Zbl 0504.10007
[13] Stanley, R. P., Enumerative Combinatorics, vol. 2 (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0928.05001
[14] Wolfram, S., A New Kind of Science (2002), Wolfram Media: Wolfram Media Champaign, IL, pp. 870; 931-932
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.