Liu, Shu-Chung; Yeh, Jean C.-C. Catalan numbers modulo \(2^k\). (English) Zbl 1230.05013 J. Integer Seq. 13, No. 5, Article ID 10.5.4, 26 p. (2010). Summary: We develop a systematic tool to calculate the congruences of some combinatorial numbers involving \(n!\). Using this tool, we re-prove Kummer’s and Lucas’ theorems in a unique concept, and classify the congruences of the Catalan numbers \(c_n\pmod {64}\). To achieve the second goal, \(c_n\pmod 8\) and \(c_n\pmod{16}\) are also classified. Through the approach of these three congruence problems, we develop several general properties. For instance, a general formula with powers of 2 and 5 can evaluate \(c_n\pmod {2^k}\) for any \(k\). An equivalence \(c_n\equiv_{2^k} c_{\bar{n}}\) is derived, where \(\bar{n}\) is the number obtained by partially truncating some runs of 1 and runs of 0 in the binary string \([n]_2\). By this equivalence relation, we show that not every number in \([0,2^k-1]\) turns out to be a residue of \(c_n \pmod {2^k}\) for \(k\geq 2\). Cited in 2 ReviewsCited in 4 Documents MSC: 05A10 Factorials, binomial coefficients, combinatorial functions 11B50 Sequences (mod \(m\)) Keywords:prime power modulus; Catalan numbers; Kummer’s theorem; Lucas’ theorem PDFBibTeX XMLCite \textit{S.-C. Liu} and \textit{J. C. C. Yeh}, J. Integer Seq. 13, No. 5, Article ID 10.5.4, 26 p. (2010; Zbl 1230.05013) Full Text: EuDML EMIS Online Encyclopedia of Integer Sequences: a(n) = n minus (number of 1’s in binary expansion of n). Also highest power of 2 dividing n!. Greatest k such that 3^k divides n!. Catalan numbers read modulo 8. Asymptotic value of odd Catalan numbers mod 2^n. Catalan numbers read modulo 16.