

A025227


a(n) = a(1)*a(n1) + a(2)*a(n2) + ...+ a(n1)*a(1) for n >= 3.


26



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Series reversion of g.f. A(x) is A(x).  Michael Somos, Jul 27 2003
a(n) = number of royal paths (A006318) from (0,0) to (n1,n1) 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) = # ordered trees with n leaves in which (i) every node (= nonroot nonleaf 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.
From William Sit (wyscc(AT)sci.ccny.cuny.edu), Jun 26 2010: (Start)
a(n+1), n >= 0, is also the number of RotaBaxter 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 n1 vertices where leaves have 2 possible colors and internal nodes have 1 color.  Alexander Burstein, Mar 07 2020


REFERENCES

L. Guo and W. Sit, Enumeration of RotaBaxter Words (extended abstract), ISSAC 2006 Proceedings, 123131. [From William Sit (wyscc(AT)sci.ccny.cuny.edu), Jun 26 2010]
L. Guo and W. Sit, Enumeration of RotaBaxter 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 PseudoInvolutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.
M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv preprint arXiv:1410.5747 [math.CO], 2014.
L. Guo, W. Y. Sit, Enumeration and generating functions of RotaBaxter Words, Math. Comput. Sci. 4 (2010) 313337
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 655
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 657
D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301320.


FORMULA

a(n) = sum(C(nk1)*binomial(nk, k), k=0..floor(n/2)), where C(q)=binomial(2q, q)/(q+1) are the Catalan numbers (A000108).  Emeric Deutsch, Nov 14 2001
Dfinite with recurrence n*a(n) = (4n6)*a(n1)+(4n12)*a(n2), 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..n1, C(k)C(k+1, nk1)}  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.: (1sqrt(14x4x^2))/2 = 2(x+x^2)/(1+sqrt(14x4x^2)).  Michael Somos, Jun 08 2000
Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t1}], we may define an infinite sequence Phi(u) by setting a_n = a_{n1} + a_0*a_{n1} + a_1*a_{n2} + ... + a_{n2}*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 nth column of the table R(m,n)=binomial(m+1, nm)c(m) where c(m) is the mth Catalan number A000108.
The table entry is nonzero if and only if m <= n <= 2m+1.
R(m,n) gives the number of RotaBaxter 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) ~ (2+2*sqrt(2))^n*sqrt((2sqrt(2))/Pi)/(2*n)^(3/2).  Vaclav Kotesovec, Aug 18 2013
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


EXAMPLE

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


MATHEMATICA

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


PROG

(PARI) a(n)=polcoeff((1sqrt(14*x4*x^2+x*O(x^n)))/2, n)


CROSSREFS

a(n) = A052709(n) + A052709(n1).
A100238(n) = (1)^n*a(n), for n>1.
Cf. A182399, A219534, A000108, A006318.
Sequence in context: A300652 A028329 A204678 * A211965 A119430 A074034
Adjacent sequences: A025224 A025225 A025226 * A025228 A025229 A025230


KEYWORD

nonn


AUTHOR

Clark Kimberling


STATUS

approved



