cp's OEIS Frontend

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

%I A025227 #111 May 16 2025 00:56:30
%S A025227 0,1,2,4,12,40,144,544,2128,8544,35008,145792,615296,2625792,11311616,
%T A025227 49124352,214838528,945350144,4182412288,18593224704,83015133184,
%U A025227 372090122240,1673660915712,7552262979584,34178799378432,155096251351040,705533929816064
%N A025227 a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ... + a(n-1)*a(1) for n >= 3.
%C A025227 Series reversion of g.f. A(x) is -A(-x). - _Michael Somos_, Jul 27 2003
%C A025227 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
%C A025227 From _David Callan_, Sep 25 2006: (Start)
%C A025227 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
%C A025227               |
%C A025227      /\      / \
%C A025227       /\       /\
%C A025227 and their mirror images. (End)
%C A025227 From William Sit (wyscc(AT)sci.ccny.cuny.edu), Jun 26 2010: (Start)
%C A025227 a(n+1), n >= 0, is also the number of Rota-Baxter words in one idempotent generator x and one operator of arity n.
%C A025227 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)
%C A025227 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
%D A025227 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]
%D A025227 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]
%H A025227 Michael De Vlieger, <a href="/A025227/b025227.txt">Table of n, a(n) for n = 0..1470</a>
%H A025227 Paul Barry, <a href="https://arxiv.org/abs/1807.05794">Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences</a>, arXiv:1807.05794 [math.CO], 2018.
%H A025227 Alexander Burstein and Louis W. Shapiro, <a href="https://arxiv.org/abs/2112.11595">Pseudo-involutions in the Riordan group</a>, arXiv:2112.11595 [math.CO], 2021.
%H A025227 Bérénice Delcroix-Oger and Clément Dupont, <a href="https://arxiv.org/abs/2505.06094">Lie-operads and operadic modules from poset cohomology</a>, arXiv:2505.06094 [math.CO], 2025. See p. 22.
%H A025227 Maciej Dziemianczuk, <a href="http://arxiv.org/abs/1410.5747">On Directed Lattice Paths With Additional Vertical Steps</a>, arXiv preprint arXiv:1410.5747 [math.CO], 2014.
%H A025227 Li Guo and William Y. Sit, <a href="http://dx.doi.org/10.1007/s11786-010-0061-2">Enumeration and generating functions of Rota-Baxter Words</a>, Math. Comput. Sci. 4 (2010) 313-337.
%H A025227 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=655">Encyclopedia of Combinatorial Structures 655</a>
%H A025227 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=657">Encyclopedia of Combinatorial Structures 657</a>
%H A025227 Donatella Merlini, Douglas G. Rogers, Renzo Sprugnoli, and M. Cecilia Verri, <a href="http://dx.doi.org/10.4153/CJM-1997-015-x">On some alternative characterizations of Riordan arrays</a>, Canad. J. Math., 49 (1997), 301-320.
%F A025227 a(n) = A052709(n) + A052709(n-1).
%F A025227 A100238(n) = -(-1)^n*a(n), for n>1.
%F A025227 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)}_{n>=0} = row sum of A068763. - _Wolfdieter Lang_, Jan 21 2023]
%F A025227 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.
%F A025227 G.f. satisfies A(x)-A(x)^2 = x+x^2. - _Ralf Stephan_, Jun 30 2003
%F A025227 a(n) = Sum_{k=0..n-1} C(k)*C(k+1, n-k-1). - _Paul Barry_, Feb 23 2005
%F A025227 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
%F A025227 G.f.: (1-sqrt(1-4x-4x^2))/2 = 2(x+x^2)/(1+sqrt(1-4x-4x^2)). - _Michael Somos_, Jun 08 2000
%F A025227 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
%F A025227 From William Sit (wyscc(AT)sci.ccny.cuny.edu), Jun 26 2010: (Start)
%F A025227 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.
%F A025227 The table entry is nonzero if and only if m <= n <= 2m+1.
%F A025227 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)
%F A025227 G.f.: A(x) = B(B(x)) where B(x) is the g.f. of A182399. -_Paul D. Hanna_, Apr 27 2012
%F A025227 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
%F A025227 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
%F A025227 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
%F A025227 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
%F A025227 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
%e A025227 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
%t A025227 Table[CatalanNumber[n-1] Hypergeometric2F1[(1-n)/2, -n/2, 3/2-n, -1] + KroneckerDelta[n], {n, 0, 20}] (* _Vladimir Reshetnikov_, May 17 2016 *)
%o A025227 (PARI) a(n)=polcoeff((1-sqrt(1-4*x-4*x^2+x*O(x^n)))/2,n)
%Y A025227 Cf. A052709, A052709, A100238.
%Y A025227 Cf. A182399, A219534, A000108, A006318.
%Y A025227 Cf. A068763.
%K A025227 nonn,easy
%O A025227 0,3
%A A025227 _Clark Kimberling_