A Short Approach to Catalan Numbers Modulo 2^r - Xin, Guoce; Xu, Jing-Feng (The Electronic Journal of Combinatorics, 2011)
We notice that two combinatorial interpretations of the well-known Catalan numbers C_n=(2n)!/n!(n+1)! naturally give rise to a recursion for C_n. This recursion is ideal for the study of the congruences of C_n modulo 2^r, which attracted a lot of interest recently. We present short proofs of some known results, and improve Liu and Yeh’s recent classification of C_n modulo 2^r. The equivalence C_n_2^r C_n is further reduced to C_n_2^r C_n for simpler n. Moreover, by using connections between weighted Dyck paths and Motzkin paths, we find new classes of combinatorial sequences whose 2-adic order is equal to that of C_n, which is one less than the sum of the digits of the binary expansion of n+1.