A025242 Generalized Catalan numbers A(x)^2 -(1+x)^2*A(x) +x*(2+x+x^2) =0.

2, 1, 1, 2, 5, 13, 35, 97, 275, 794, 2327, 6905, 20705, 62642, 190987, 586219, 1810011, 5617914, 17518463, 54857506, 172431935, 543861219, 1720737981, 5459867166, 17369553427, 55391735455, 177040109419, 567019562429, 1819536774089

Offset: 1

Author

Clark Kimberling, Olivier Gérard

Keywords

• nonn
• easy

Comments

Number of Dyck paths of semilength n-1 with no UUDD (n>1). Example: a(4)=2 because the only Dyck paths of semilength 3 with no UUDD in them are UDUDUD and UUDUDD (the nonqualifying ones being UDUUDD, UUDDUD and UUUDDD). - Emeric Deutsch, Jan 27 2003

a(n) is the number of Dyck (n-2)-paths with no DDUU (n>2). Example: a(6)=13 counts all 14 Dyck 4-paths except UUDDUUDD which contains a DDUU. There is a simple bijective proof: given a Dyck path that avoids DDUU, for every occurrence of UUDD except the first, the ascent containing this UU must be immediately preceded by a UD (else a DDUU would be present). Transfer the latter UD to the middle of the DD in the UUDD. Then insert a new UD in the middle of the first DD if any; if not, the path is a sawtooth UDUD...UD, in which case insert a UD at the end. This is a bijection from DDUU-avoiding Dyck n-paths to UUDD-avoiding Dyck (n+1)-paths. - David Callan, Sep 25 2006

For n>1, a(n) is the number of cyclic permutations of [n-1] that avoid the vincular pattern 13-4-2, i.e., the pattern 1342 where the 1 and 3 must be adjacent. By the trivial Wilf equivalence, the same applies for 24-3-1, 31-2-4, and 42-1-3. - Rupert Li, Jul 27 2021

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• Sela Fried, Even-up words and their variants, arXiv:2505.14196 [math.CO], 2025. See p. 10.
• Petr Gregor, Torsten Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, arXiv:2306.08420 [cs.DM], 2023.
• Petr Gregor, Torsten Mütze, and Namrata, Pattern-Avoiding Binary Trees-Generation, Counting, and Bijections, Leibniz Int'l Proc. Informatics (LIPIcs), 34th Int'l Symp. Algor. Comp. (ISAAC 2023). See p. 33.13.
• Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
• Jia Huang and Erkko Lehtonen, Associative-commutative spectra for some varieties of groupoids, arXiv:2401.15786 [math.CO], 2024. See p. 18.
• Vít Jelínek, Toufik Mansour and Mark Shattuck, On multiple pattern avoiding set partitions, Adv. Appl. Math. 50 (2) (2013) 292-326, Theorem 4.1, without the leading 2.
• Yvan Le Borgne, Counting Upper Interactions in Dyck Paths, Séminaire Lotharingien de Combinatoire, Vol. 54, B54f (2006), 16 pp.
• Rupert Li, Vincular Pattern Avoidance on Cyclic Permutations, arXiv:2107.12353 [math.CO], 2021.
• Toufik Mansour, Restricted 1-3-2 permutations and generalized patterns, arXiv:math/0110039 [math.CO], 2001.
• Toufik Mansour, Restricted 1-3-2 permutations and generalized patterns, Annals of Combin., 6 (2002), 65-76. (Example 2.10.)
• Toufik Mansour and Mark Shattuck, Restricted partitions and generalized Catalan numbers, PU. M. A., Vol. (2011), No. 2, pp. 239-251. - From _N. J. A. Sloane_, Oct 13 2012
• Lara Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015.
• Lara Pudwell and Andrew Baxter, Ascent sequences avoiding pairs of patterns, Slides, Permutation Patterns 2014, East Tennessee State University Jul 07 2014.
• A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Crossrefs

Cf. A000108, A001006, A006318, A004148, A007477, A082582, A086581.

Programs

Mathematica

a[ 0 ]=1; a[ n_Integer ] := a[ n ]=a[ n-1 ]+Sum[ a[ k ]*a[ n-1-k ], {k, 2, n-1} ];

PARI

a(n)=polcoeff((1+2*x+x^2-sqrt(1-4*x+2*x^2+x^4+x*O(x^n)))/2,n)

Formula

a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ... + a(n-3)*a(3) for n >= 4.

G.f.: (1+2*x+x^2-sqrt(1-4*x+2*x^2+x^4))/2. - Michael Somos, Jun 08 2000

Conjecture: n*(n+1)*a(n) +(n^2+n+2)*a(n-1) +2*(-9*n^2+15*n+17)*a(n-2) +2*(5*n+4)*(n-4)*a(n-3) +(n+1)*(n-6)*a(n-4) +(5*n+4)*(n-7)*a(n-5)=0. - R. J. Mathar, Jan 12 2013

G.f.: 2 + x - x*G(0), where G(k) = 1 - 1/(1 - x/(1 - x/(1 - x/(1 - x/(x - 1/G(k+1) ))))); (continued fraction). - Sergei N. Gladkovskii, Jul 12 2013