|
| |
|
|
A025227
|
|
a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ...+ a(n-1)*a(1) for n >= 3.
|
|
18
| |
|
|
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; 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 (callan(AT)stat.wisc.edu), Jul 03 2006
Comments from David Callan (callan(AT)stat.wisc.edu), Sep 25 2006: 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.
Contribution 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 non-zero 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
| 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 (deutsch(AT)duke.poly.edu), Nov 14 2001
na(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 (ralf(AT)ark.in-berlin.de), Jun 30 2003
a(n)=sum{k=0..n-1, C(k)C(k+1, n-k-1)} - Paul Barry (pbarry(AT)wit.ie), 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
Comment from Gary W. Adamson (qntmpkt(AT)yahoo.com), Oct 27 2008: 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]).
Contribution 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 non-zero if and only if m <= n <= 2m+1.
R(m,n) counts 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 non-zero count),
such that no two pairs of parentheses are immediately nested and no two x's remain adjacent. (End)
|
|
|
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. [From William Sit (wyscc(AT)sci.ccny.cuny.edu), Jun 26 2010]
|
|
|
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), if n>1.
Sequence in context: A056236 A028329 A204678 * A119430 A074034 A188479
Adjacent sequences: A025224 A025225 A025226 * A025228 A025229 A025230
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Clark Kimberling (ck6(AT)evansville.edu)
|
| |
|
|
