login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A025227 a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ...+ a(n-1)*a(1) for n >= 3. 25
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 (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) = # 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.

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)

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.

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 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

a(n) = sum(C(n-k-1)*binomial(n-k, k), k=0..floor(n/2)), where C(q)=binomial(2q, q)/(q+1) are the Catalan numbers (A000108). - Emeric Deutsch, Nov 14 2001

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) ~ (2+2*sqrt(2))^n*sqrt((2-sqrt(2))/Pi)/(2*n)^(3/2). - Vaclav Kotesovec, Aug 18 2013

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

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

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

Cf. A182399, A219534.

Sequence in context: A300652 A028329 A204678 * A211965 A119430 A074034

Adjacent sequences:  A025224 A025225 A025226 * A025228 A025229 A025230

KEYWORD

nonn,changed

AUTHOR

Clark Kimberling

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 20 01:39 EDT 2018. Contains 316378 sequences. (Running on oeis4.)