|
| |
|
|
A155069
|
|
Expansion of (3 - x - sqrt(1 - 6*x + x^2))/2.
|
|
7
|
|
|
|
1, 1, 2, 6, 22, 90, 394, 1806, 8558, 41586, 206098, 1037718, 5293446, 27297738, 142078746, 745387038, 3937603038, 20927156706, 111818026018, 600318853926, 3236724317174, 17518619320890, 95149655201962, 518431875418926
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
a(n) is also the number of "branching configurations" for RNA (see Sankoff, 1985) that have exactly n hairpins. - Lee A. Newberg, Mar 30 2010
a(n) is also the number of ways to insert balanced parentheses into a product of n variables such that each parenthesis pair has 2 or more top-level factors. - Lee A. Newberg, Apr 06 2010
a(n) is also the number of infix expressions with n variables and operators + and - such that there are no redundant parentheses. - Vjeran Crnjak, Apr 25 2020
a(n) is also the number of permutations on n elements that can be obtained with an output-restricted (or input-restricted) deque. (see D. E. Knuth: The Art of Computer Programming, Volume 1, page 539). - Zhujun Zhang, Oct 15 2023
|
|
|
REFERENCES
|
S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7
D. E. Knuth, The Art of Computer Programming, Volume 1, Fundamental Algorithms, section 2.2.1: Stacks, Queues, and Deques.
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: (3 - x - sqrt(1 -6*x +x^2))/2.
G.f.: 4 / (3 - x + sqrt(1 - 6*x + x^2)). - Michael Somos, Apr 18 2012
a(n) ~ sqrt((sqrt(18)-4)/(4*Pi)) * n^(-3/2) * (3 + sqrt(8))^n, which is, approximately, a(n) ~ 0.1389558648 * n^(-1.5) * 5.828427125^n. - Lee A. Newberg, Apr 06 2010
a(n) ~ (1 + sqrt(2))^(2*n-1) / (2^(3/4)*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 23 2023
a(n) = top left term of M^n, where M = the production matrix:
1, 1, 0, 0, 0, ...
1, 2, 1, 0, 0, ...
1, 2, 2, 1, 0, ...
1, 2, 2, 2, 1, ...
1, 2, 2, 2, 2, 1, ...
...
G.f.: A(x)=(3 -x- sqrt(1-6*x+x^2))/2= 2 - G(0); G(k)= 1 + x - 2*x/G(k+1); (continued fraction, 1-step, 1 var.). - Sergei N. Gladkovskii, Jan 04 2012
G.f.: A(x)=(3 -x -sqrt(1-6*x+x^2))/2= G(0); G(k)= := 1 - x/(1 - 2/G(k+1)); (continued fraction, 2-step, 2 var.). - Sergei N. Gladkovskii, Jan 04 2012
D-finite with recurrence: n*a(n) +3*(3-2*n)*a(n-1) +(n-3)*a(n-2)=0. - R. J. Mathar, Jul 24 2012
G.f.: 1 / (1 - x / (1 - x / (1 - 2*x / (1 - x / (1 - 2*x / (1 - x / ... )))))) = 1 + x / (1 - 2*x / (1 - x / (1 - 2*x / (1 - x / (1 - 2*x / (1 - x / ... )))))). - Michael Somos, Jan 03 2013
G.f.: 2 - x - G(0), where G(k)= k+1 - 2*x*(k+1) - 2*x*(k+1)*(k+2)/G(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Jul 14 2013
a(n) = (1/n)*Sum_{i = 0..n/2} binomial(n+i-1,i)* binomial(2*n, n-2*i-1)), n>0, a(0)=1. - Vladimir Kruchinin, Nov 13 2014
a(n) = Catalan(n)*hypergeometric([1/2-n/2, 1-n/2, n], [n/2+1, n/2+3/2], 1). - Peter Luschny, Nov 14 2014
a(0) = 1; a(n) = a(n-1) + Sum_{k=1..n-1} a(k) * a(n-k). - Ilya Gutkovskiy, Apr 11 2021
|
|
|
EXAMPLE
|
For n = 2, the a(2) = 2 branching configurations are ()() and (()()), where each () indicates a hairpin (also termed 1-loop) and each other pair of parentheses indicates a k-loop for k >= 3.
For n = 3, the a(3) = 6 branching configurations are ()()(), (()())(), ()(()()), (()()()), ((()())()), and (()(()())). (End)
When inserting balanced parentheses into the product x^n: For n = 0, the a(0) = 1 possible term is the empty term. For n = 1, the a(1) = 1 possible term is x. For n = 2, the a(2) = 2 possible terms are xx and (xx). For n = 3, the a(3) = 6 possible terms are xxx, (xx)x, x(xx), (xxx), ((xx)x), and (x(xx)). - Lee A. Newberg, Apr 06 2010
G.f. = 1 + x + 2*x^2 + 6*x^3 + 22*x^4 + 90*x^5 + 394*x^6 + 1806*x^7 + ...
|
|
|
MAPLE
|
seq(coeff(series((3-x -sqrt(1-6*x+x^2))/2, x, n+1), x, n), n = 0..25); # G. C. Greubel, Jun 08 2020
|
|
|
MATHEMATICA
|
CoefficientList[Series[(3 -x -Sqrt[1-6x+x^2])/2, {x, 0, 25}], x] (* Vincenzo Librandi, Nov 13 2014 *)
|
|
|
PROG
|
(Maxima)
a(n):=if n<1 then 1 else sum(binomial(n+i-1, i)* binomial(2*n, n-2*i-1), i, 0, (n)/2)/(n); /* Vladimir Kruchinin, Nov 13 2014 */
(Sage)
a = lambda n: catalan_number(n)*hypergeometric([1/2-n/2, 1-n/2, n], [n/2+1, n/2+3/2], 1)
print([simplify(a(n)) for n in (0..25)]) # Peter Luschny, Nov 14 2014
(Magma) R<x>:=PowerSeriesRing(Rationals(), 25); Coefficients(R!( (3-x-Sqrt(1-6*x+x^2))/2 )); // G. C. Greubel, Jun 08 2020
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
