|
%I #83 Oct 23 2023 08:30:34
%S 1,1,2,6,22,90,394,1806,8558,41586,206098,1037718,5293446,27297738,
%T 142078746,745387038,3937603038,20927156706,111818026018,600318853926,
%U 3236724317174,17518619320890,95149655201962,518431875418926
%N Expansion of (3 - x - sqrt(1 - 6*x + x^2))/2.
%C A minor variation of A006318. Unsigned version of A086456 and A103137. The Hankel transform of this sequence is A006125.
%C 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
%C 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
%C 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
%C 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
%D S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7
%D D. E. Knuth, The Art of Computer Programming, Volume 1, Fundamental Algorithms, section 2.2.1: Stacks, Queues, and Deques.
%H Michael De Vlieger, <a href="/A155069/b155069.txt">Table of n, a(n) for n = 0..1313</a>
%H J. Abate and W. Whitt, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Whitt/whitt2.html">Integer Sequences from Queueing Theory </a>, J. Int. Seq. 13 (2010), 10.5.5, Theorem 5.
%H Paul Barry, <a href="http://dx.doi.org/10.1016/j.laa.2015.10.032">Riordan arrays, generalized Narayana triangles, and series reversion</a>, Linear Algebra and its Applications, 491 (2016) 343-385.
%H Christian Bean, <a href="https://hdl.handle.net/20.500.11815/1184">Finding structure in permutation sets</a>, Ph.D. Dissertation, Reykjavík University, School of Computer Science, 2018.
%H D. Sankoff, <a href="https://web.archive.org/web/20100625104527/http://www.genetics.wustl.edu/compgen-disc/sankoff.pdf">Simultaneous solution of the RNA folding, alignment and protosequence problems</a>, Siam J. Appl. Math 45(5):810-825 (1985). [From _Lee A. Newberg_, Mar 30 2010]
%F G.f.: (3 - x - sqrt(1 -6*x +x^2))/2.
%F G.f.: 4 / (3 - x + sqrt(1 - 6*x + x^2)). - _Michael Somos_, Apr 18 2012
%F 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
%F a(n) ~ (1 + sqrt(2))^(2*n-1) / (2^(3/4)*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 23 2023
%F a(n) = top left term of M^n, where M = the production matrix:
%F 1, 1, 0, 0, 0, ...
%F 1, 2, 1, 0, 0, ...
%F 1, 2, 2, 1, 0, ...
%F 1, 2, 2, 2, 1, ...
%F 1, 2, 2, 2, 2, 1, ...
%F ...
%F Top row terms of M^n generates rows of triangle A132372. - _Gary W. Adamson_, Jul 07 2011
%F 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
%F 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
%F 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
%F 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
%F 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
%F 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
%F 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
%F a(0) = 1; a(n) = a(n-1) + Sum_{k=1..n-1} a(k) * a(n-k). - _Ilya Gutkovskiy_, Apr 11 2021
%e From _Lee A. Newberg_, Mar 30 2010: (Start)
%e 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.
%e For n = 3, the a(3) = 6 branching configurations are ()()(), (()())(), ()(()()), (()()()), ((()())()), and (()(()())). (End)
%e 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
%e G.f. = 1 + x + 2*x^2 + 6*x^3 + 22*x^4 + 90*x^5 + 394*x^6 + 1806*x^7 + ...
%p 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
%t CoefficientList[Series[(3 -x -Sqrt[1-6x+x^2])/2, {x, 0, 25}], x] (* _Vincenzo Librandi_, Nov 13 2014 *)
%o (Maxima)
%o 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 */
%o (Sage)
%o a = lambda n: catalan_number(n)*hypergeometric([1/2-n/2,1-n/2,n],[n/2+1,n/2+3/2],1)
%o print([simplify(a(n)) for n in (0..25)]) # _Peter Luschny_, Nov 14 2014
%o (Magma) R<x>:=PowerSeriesRing(Rationals(), 25); Coefficients(R!( (3-x-Sqrt(1-6*x+x^2))/2 )); // _G. C. Greubel_, Jun 08 2020
%Y Cf. A006318, A085403, A086456, A103137, A132372.
%K nonn
%O 0,3
%A _Philippe Deléham_, Nov 02 2009
|
