Journal of Integer Sequences, Vol. 13 (2010), Article 10.5.4

Catalan Numbers Modulo 2k


Shu-Chung Liu
Department of Applied Mathematics
National Hsinchu University of Education
Hsinchu, Taiwan

and

Jean C.-C. Yeh
Department of Mathematics
Texas A & M University
College Station, TX 77843-3368
USA

Abstract:

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$.

Full version:  pdf,    dvi,    ps,    latex    

Received January 14 2010; revised version received April 30 2010. Published in Journal of Integer Sequences, May 3 2010.

Return to Journal of Integer Sequences home page