OFFSET
0,3
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
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.
M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv preprint arXiv:1410.5747 [math.CO], 2014.
L. Guo and W. 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
D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320.
FORMULA
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)}_{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
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[n-1] Hypergeometric2F1[(1-n)/2, -n/2, 3/2-n, -1] + KroneckerDelta[n], {n, 0, 20}] (* Vladimir Reshetnikov, May 17 2016 *)
PROG
(PARI) a(n)=polcoeff((1-sqrt(1-4*x-4*x^2+x*O(x^n)))/2, n)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
STATUS
approved