×

A short approach to Catalan numbers modulo \(2^r\). (English) Zbl 1234.05018

Summary: 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 \equiv _{2^r} C_{\bar n}\) is further reduced to \(C_n \equiv _{2^r} C_{\tilde n}\) for simpler \(\tilde 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\).

MSC:

05A10 Factorials, binomial coefficients, combinatorial functions
11B50 Sequences (mod \(m\))
PDFBibTeX XMLCite
Full Text: EMIS