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

0, 1, 2, 4, 12, 40, 144, 544, 2128, 8544, 35008, 145792, 615296, 2625792, 11311616, 49124352, 214838528, 945350144, 4182412288, 18593224704, 83015133184, 372090122240, 1673660915712, 7552262979584, 34178799378432, 155096251351040, 705533929816064

Offset: 0

Author

Clark Kimberling

Keywords

• nonn
• easy

Comments

Series reversion of g.f. A(x) is -A(-x). - Michael Somos, Jul 27 2003

a(n) is the number of royal paths (A006318) from (0,0) to (n-1,n-1) such that every northeast (diagonal) step is either immediately followed by a north step or ends the path. For example a(3)=4 counts EDN, EENN, END, ENEN (E=east, D=diagonal, N=north). - David Callan, Jul 03 2006

From David Callan, Sep 25 2006: (Start)

a(n) is the number of ordered trees with n leaves in which (i) every node (= non-root non-leaf vertex) has at least 2 children and (ii) each leaf is either the leftmost or rightmost child of its parent. For example, a(3)=4 counts

|

/\ / \

/\ /\

and their mirror images. (End)

From William Sit (wyscc(AT)sci.ccny.cuny.edu), Jun 26 2010: (Start)

a(n+1), n >= 0, is also the number of Rota-Baxter words in one idempotent generator x and one operator of arity n.

Alternatively, a(n+1) is the number of ways of adding pairs of parentheses to a string of n x's (the number m of parentheses pairs necessarily satisfies m <= n <= 2m+1 for a nonzero count), such that no two pairs of parentheses are immediately nested and no two x's remain adjacent. (End)

a(n) is the number of colored binary trees on n-1 vertices where leaves have 2 possible colors and internal nodes have 1 color. - Alexander Burstein, Mar 07 2020

Examples

			For n=2, a(3) = 4 has the following words: x(x), (x)x, (x(x)), ((x)x) corresponding to A(1,2)=2, and A(2,2)=2. - William Sit (wyscc(AT)sci.ccny.cuny.edu), Jun 26 2010
		

References

• L. Guo and W. Sit, Enumeration of Rota-Baxter Words (extended abstract), ISSAC 2006 Proceedings, 123-131. [From William Sit (wyscc(AT)sci.ccny.cuny.edu), Jun 26 2010]
• L. Guo and W. Sit, Enumeration of Rota-Baxter Words, to appear in Mathematics in Computer Science, Special Issue on AADIOS special session, ACA, 2009. [From William Sit (wyscc(AT)sci.ccny.cuny.edu), Jun 26 2010]

Links

• Michael De Vlieger, Table of n, a(n) for n = 0..1470
• Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.
• Alexander Burstein and Louis W. Shapiro, Pseudo-involutions in the Riordan group, arXiv:2112.11595 [math.CO], 2021.
• Bérénice Delcroix-Oger and Clément Dupont, Lie-operads and operadic modules from poset cohomology, arXiv:2505.06094 [math.CO], 2025. See p. 22.
• Maciej Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv preprint arXiv:1410.5747 [math.CO], 2014.
• Li Guo and William Y. Sit, Enumeration and generating functions of Rota-Baxter Words, Math. Comput. Sci. 4 (2010) 313-337.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 655
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 657
• Donatella Merlini, Douglas G. Rogers, Renzo Sprugnoli, and M. Cecilia Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320.

Crossrefs

Cf. A052709, A052709, A100238.

Cf. A182399, A219534, A000108, A006318.

Cf. A068763.

Programs

Mathematica

Table[CatalanNumber[n-1] Hypergeometric2F1[(1-n)/2, -n/2, 3/2-n, -1] + KroneckerDelta[n], {n, 0, 20}] (* Vladimir Reshetnikov, May 17 2016 *)

PARI

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

Formula

a(n) = A052709(n) + A052709(n-1).

A100238(n) = -(-1)^n*a(n), for n>1.

a(n) = Sum_{k=0..floor(n/2)} C(n-k-1)*binomial(n-k, k), where C(q)=binomial(2q, q)/(q+1) are the Catalan numbers (A000108). - Emeric Deutsch, Nov 14 2001 [{a(n+1)}A068763.%20-%20_Wolfdieter%20Lang">{n>=0} = row sum of A068763. - _Wolfdieter Lang, Jan 21 2023]

D-finite with recurrence n*a(n) = (4n-6)*a(n-1)+(4n-12)*a(n-2), n>2. a(1)=1, a(2)=2.

G.f. satisfies A(x)-A(x)^2 = x+x^2. - Ralf Stephan, Jun 30 2003

a(n) = Sum_{k=0..n-1} C(k)*C(k+1, n-k-1). - Paul Barry, Feb 23 2005

G.f. A(x) satisfies A(x)=x+C(2x*A(x)) where C(x) is g.f. of Catalan numbers A000108 offset 1. - Michael Somos, Sep 08 2005

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

Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t-1}], we may define an infinite sequence Phi(u) by setting a_n = a_{n-1} + a_0*a_{n-1} + a_1*a_{n-2} + ... + a_{n-2}*a_1 for n >= t. For example Phi([1]) is the Catalan numbers A000108. The present sequence is (essentially) Phi([1,2]). - Gary W. Adamson, Oct 27 2008

From William Sit (wyscc(AT)sci.ccny.cuny.edu), Jun 26 2010: (Start)

a(n+1), n >= 0, is column sum for the n-th column of the table R(m,n)=binomial(m+1, n-m)c(m) where c(m) is the m-th Catalan number A000108.

The table entry is nonzero if and only if m <= n <= 2m+1.

R(m,n) gives the number of Rota-Baxter words in one idempotent generator x and one operator of degree m and arity n, or the number of ways of adding m pairs of parentheses to a string of n x's (n necessarily lies between m and 2m+1 inclusive for a nonzero count), such that no two pairs of parentheses are immediately nested and no two x's remain adjacent. (End)

G.f.: A(x) = B(B(x)) where B(x) is the g.f. of A182399. -Paul D. Hanna, Apr 27 2012

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

a(n) ~ (1 + sqrt(2))^(n - 1/2) * 2^(n - 5/4) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Aug 18 2013, simplified Jan 21 2023

O.g.f.: A(x) = x*S(x/(1 + x)), where S(x) = (1 - x - sqrt(1 - 6*x + x^2))/(2*x) is the o.g.f. for the large Schröder numbers A006318. - Peter Bala, Mar 05 2020

G.f.: A(x) satisfies ((A(x) - A(-x))/(2*x))^2 = S(4*x^2), where S(x) is the g.f. for the large Schröder numbers A006318. - Alexander Burstein, May 20 2021

A(x) = (x + x^2)*c(x+x^2), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the g.f. of the Catalan numbers A000108. Note that (x - x^2)*c(x-x^2) = x. - Peter Bala, Aug 29 2024