Catalan numbers modulo \(2^k\)
Journal of integer sequences, Tome 13 (2010) no. 5
In this paper, 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 (mod 64)$. To achieve the second goal, $c_n (mod 8)$ and $c_n (mod 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 (mod 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 (mod 2^k)$ for $k\ge 2$.
Classification :
05A10, 11B50
Keywords: prime power modulus, Catalan numbers, Kummer's theorem, Lucas theorem
Keywords: prime power modulus, Catalan numbers, Kummer's theorem, Lucas theorem
@article{JIS_2010__13_5_a3,
author = {Liu, Shu-Chung and Yeh, Jean C.-C.},
title = {Catalan numbers modulo \(2^k\)},
journal = {Journal of integer sequences},
year = {2010},
volume = {13},
number = {5},
zbl = {1230.05013},
language = {en},
url = {http://geodesic.mathdoc.fr/item/JIS_2010__13_5_a3/}
}
Liu, Shu-Chung; Yeh, Jean C.-C. Catalan numbers modulo \(2^k\). Journal of integer sequences, Tome 13 (2010) no. 5. http://geodesic.mathdoc.fr/item/JIS_2010__13_5_a3/