login
A157418
a(n) is the number of ways to insert single pairs of parenthesis to completely separate n identical objects in a straight line such that at least one of the objects at the two ends is not enclosed.
1
1, 2, 5, 16, 55, 202, 773, 3052, 12339, 50830, 212593, 900368, 3853551, 16641554, 72423661, 317312532, 1398490091, 6195882006, 27578607593, 123270393880, 553075982311, 2489989595162, 11245131702245, 50929608736796
OFFSET
1,2
COMMENTS
a(n) is also the number of associate Rota-Baxter words in one idempotent generator x and one idempotent operator in which x appears n times (idempotent is also known as the exponent 1 case). An associate Rota-Baxter word in this case is a parenthesized expression in x which either begins or ends in x (or both). It is related to counting other (bracketed, decomposable, indecomposable) Rota-Baxter words and is a special case of a(m,n) when the number m of pairs of parenthesis is unrestricted.
REFERENCES
L. Guo and W. Sit, Enumeration of Rota-Baxter Words (extended abstract), ISSAC (International Symposium on Symbolic and Algebraic Computations) 2006 Proceedings, 124-131.
LINKS
L. Guo, W. Y. Sit, Enumeration and generating functions of Rota-Baxter Words, Math. Comput. Sci. 4 (2010) 313-337
FORMULA
G.f.: (2-t-2t^2-(t+2)*sqrt(1-4t-4t^2))/(2(t+1)^2).
Conjecture: n*(7*n-29)*a(n) +(-21*n^2+136*n-192)*a(n-1) +2*(-28*n^2+165*n-210)*a(n-2) -4*(n-3)*(7*n-22)*a(n-3)=0. - R. J. Mathar, Jul 24 2012
a(n) ~ 7/sqrt(146+103*sqrt(2)) * (2+2*sqrt(2))^n/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 20 2012
EXAMPLE
Let x denote the object.
For n=1, the a(1) = 1 solution is: x.
For n=2, the a(2) = 2 solutions are (x)x and x(x).
For n=3, the a(3) = 5 solutions are ((x)x)x, (x(x))x, x((x)x), x(x)x, x(x(x)).
MATHEMATICA
genfun[t_]:=(2-t-2t^2-(t+2)Sqrt[1-4t-4t^2])/(2(t+1)^2); a[n_] := Coefficient[Series[genfun[t], {t, 0, n}], t, n]; a[5]
Rest@ CoefficientList[ Series[(2 - x - 2x^2 - (x + 2)Sqrt[1 - 4x - 4x^2])/(2(x + 1)^2), {x, 0, 24}], x] (* Robert G. Wilson v, Jun 27 2010 *)
CROSSREFS
Sequence in context: A149969 A051960 A149970 * A149971 A176828 A149972
KEYWORD
nonn,easy,nice
AUTHOR
William Sit (wyscc(AT)sci.ccny.cuny.edu), Jun 25 2010
EXTENSIONS
More terms from Robert G. Wilson v and Jon E. Schoenfield, Jun 27 2010
STATUS
approved