Deutsch, Emeric; Sagan, Bruce E. Congruences for Catalan and Motzkin numbers and related sequences. (English) Zbl 1163.11310 J. Number Theory 117, No. 1, 191-215 (2006). Summary: We prove various congruences for Catalan and Motzkin numbers as well as related sequences. The common thread is that all these sequences can be expressed in terms of binomial coefficients. Our techniques are combinatorial and algebraic: group actions, induction, and Lucas’ congruence for binomial coefficients come into play. A number of our results settle conjectures of Cloitre and Zumkeller. The Thue-Morse sequence appears in several contexts. Cited in 5 ReviewsCited in 36 Documents MSC: 11B65 Binomial coefficients; factorials; \(q\)-identities 11B83 Special sequences and polynomials Software:OEIS PDFBibTeX XMLCite \textit{E. Deutsch} and \textit{B. E. Sagan}, J. Number Theory 117, No. 1, 191--215 (2006; Zbl 1163.11310) Full Text: DOI arXiv Online Encyclopedia of Integer Sequences: Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!). Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle. Central Delannoy numbers: a(n) = Sum_{k=0..n} C(n,k)*C(n+k,k). Central trinomial coefficients: largest coefficient of (1 + x + x^2)^n. Numbers whose binary representation ends in an even number of zeros. Riordan numbers: a(n) = (n-1)*(2*a(n-1) + 3*a(n-2))/(n+1). Apéry numbers: a(n) = Sum_{k=0..n} binomial(n,k)^2 * binomial(n+k,k). Number of connected graphs on n labeled nodes on a circle with straight-line edges that don’t cross. Triangle of Eulerian numbers T(n,k) (n >= 1, 1 <= k <= n) read by rows. Thue-Morse sequence: let A_k denote the first 2^k terms; then A_0 = 0 and for k >= 0, A_{k+1} = A_k B_k, where B_k is obtained from A_k by interchanging 0’s and 1’s. a(n) = A000120(n+1) - 1 = wt(n+1) - 1. a(n) = 2^(A000120(n+1) - 1), n >= 0. Revert transform of factorials n! (n >= 1). Odd numbers such that base 3 representation contains no 2. Expansion of (1/(1-x))(1+2x/(1-x+sqrt(1-2x-3x^2))). Even Motzkin numbers. Even Motzkin numbers divided by 2. References: [1] Albert, M.; Atkinson, M.; Klazar, M., The enumeration of simple permutations, J. Integer Sequences, 6 (2003), Article 03.4.4, 18pp · Zbl 1065.05001 [2] Allouche, J.-P.; Arnold, A.; Berstel, J.; Brlek, S.; Jockusch, W.; Plouffe, S.; Sagan, B. E., A relative of the Thue-Morse sequence, Discrete Math., 139, 455-461 (1995) · Zbl 0839.11007 [4] Alter, R.; Kubota, K., Prime and prime power divisibility of Catalan numbers, J. Combin. Theory Ser. A, 15, 243-256 (1973) · Zbl 0273.10010 [6] Barcucci, E.; Pinzani, R.; Sprugnoli, R., The Motzkin family, Pure Math. Appl. Ser. A, 2, 3-4, 249-279 (1991) · Zbl 0756.05003 [7] Bernhart, F., Catalan, Motzkin, and Riordan numbers, Discrete Math., 204, 73-112 (1999) · Zbl 0933.05002 [9] Chowla, S.; Cowles, J.; Cowles, M., Congruence properties of Apéry numbers, J. Number Theory, 12, 188-190 (1980) · Zbl 0428.10008 [11] Deutsch, E., An involution on Dyck paths and its consequences, Discrete Math., 204, 163-166 (1999) · Zbl 0932.05005 [12] Dickson, L. E., History of the Theory of Numbers, vol. 1 (1952), Chelsea: Chelsea New York, NY [13] Donaghey, R., Restricted plane tree representations of four Motzkin-Catalan equations, J. Combin. Theory Ser. B, 22, 114-121 (1977) · Zbl 0352.05028 [14] Donaghey, R.; Shapiro, L. W., Motzkin numbers, J. Combin. Theory Ser. A, 23, 291-301 (1977) · Zbl 0417.05007 [15] Eğecioğlu, Ö., The parity of the Catalan numbers via lattice paths, Fibonacci Quart., 21, 65-66 (1983) · Zbl 0502.05005 [16] Flajolet, P.; Noy, M., Analytic combinatorics of non-crossing configurations, Discrete Math., 204, 203-229 (1999) · Zbl 0939.05005 [17] Gessel, I. M., Some congruences for Apéry numbers, J. Number Theory, 14, 362-368 (1982) · Zbl 0482.10003 [18] Gouyou-Beauchamps, D.; Viennot, G., Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem, Adv. in Appl. Math., 9, 334-357 (1988) · Zbl 0727.05036 [19] Harary, F.; Read, R. C., The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc., 17, 1-13 (1970) · Zbl 0201.26104 [20] Hardy, G. H.; Wright, E. M., An Introduction to the Theory of Numbers (1960), Oxford University Press: Oxford University Press London · Zbl 0086.25803 [21] Kazandzidis, G. S., Congruences on the binomial coefficients, Bull. Soc. Math. Gréce (N.S.), 9, 1-12 (1968) · Zbl 0179.06601 [23] Kummer, Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen, E. E., J. Reine Angew. Math., 44, 93-146 (1852) [25] Lucas, E., Sur les congruences des nombres eulériens et des coefficients différentiels des fonctions trigonométriques suivant un module premier, Bull. Soc. Math. France, 6, 49-54 (1877-1878) · JFM 10.0139.04 [26] Mimura, Y., Congruence properties of Apéry numbers, J. Number Theory, 16, 138-146 (1983) · Zbl 0504.10007 [28] Radoux, C., Quelques propriétés arithmétiques des nombres d’Apéry, C. R. Acad. Sci. Paris Ser. A-B, 291, 567-569 (1980) · Zbl 0445.10013 [29] Sagan, B. E., Congruences via Abelian groups, J. Number Theory, 20, 210-237 (1985) · Zbl 0577.10003 [30] Schröder, E., Vier combinatorische Probleme, Z. für Math. Phys., 15, 361-376 (1870) · JFM 02.0108.04 [31] Simion, R., Noncrossing partitions, Discrete Math., 217, 367-409 (2000) · Zbl 0959.05009 [32] Simion, R.; Ullman, D., On the structure of the lattice of noncrossing partitions, Discrete Math., 98, 193-206 (1991) · Zbl 0760.05004 [34] Stanley, R. P., Enumerative Combinatorics, vol. 2 (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0928.05001 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.