|
%I #77 Jan 31 2024 08:03:30
%S 0,1,1,3,7,19,53,153,453,1367,4191,13015,40857,129441,413337,1328971,
%T 4298727,13978971,45673981,149867513,493638797,1631616239,5410015615,
%U 17990076527,59981630321,200476419713,671564145137,2254338511507,7582179238151,25547868961315
%N Expansion of (1 - x - x^2 - sqrt(1 - 2*x - 5*x^2 - 2*x^3 + x^4)) / (2*x + 2*x^2).
%C Number of irreducible stack sortable permutations of degree n.
%C Also number of Dyck paths of semilength n with no UDUD. Example: a(3)=3 because the only Dyck paths of semilength 3 with no UDUD in them are: UDUUDD, UUDDUD and UUUDDD (the nonqualifying ones being UUDUDD and UDUDUD). - _Emeric Deutsch_, Jan 27 2003
%C From _Paul Barry_, Jan 29 2009: (Start)
%C The sequence 1,1,1,3,7,19,... has general term sum{k=0..n, C(n+k,2k)*(-1)^(n-k)*A006318(k)} and g.f. given by
%C 1/(1+x-2x/(1+x-x/(1+x-2x/(1+x-x/(1+x-2x/(1+x-x/(1-..... (continued fraction). (End)
%H Vincenzo Librandi, <a href="/A078481/b078481.txt">Table of n, a(n) for n = 0..1000</a>
%H Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, <a href="http://doi.org/10.1007/978-3-319-77313-1_15">Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects</a>, in International Conference on Language and Automata Theory and Applications, S. Klein, C. Martín-Vide, D. Shapira (eds), Springer, Cham, pp 195-206, 2018.
%H Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/patterns2019.pdf">Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata</a>, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
%H M. D. Atkinson and T. Stitt, <a href="http://www.cs.otago.ac.nz/staffpriv/mike/Papers/WreathProduct/Wreathpaper.pdf">Restricted permutations and the wreath product</a>, Preprint, 2002.
%H M. D. Atkinson and T. Stitt, <a href="http://dx.doi.org/10.1016/S0012-365X(02)00443-0">Restricted permutations and the wreath product</a>, Discrete Math., 259 (2002), 19-36.
%H J.-L. Baril, <a href="https://doi.org/10.46298/dmtcs.2158">Avoiding patterns in irreducible permutations</a>, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Barry/barry601.html">On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.
%H Toufik Mansour, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Mansour/mansour86.html">Statistics on Dyck Paths</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.
%H A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.005">Counting strings in Dyck paths</a>, Discrete Math., 307 (2007), 2909-2924.
%H Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016.
%F G.f.: (1 - x - x^2 - (1 - 2*x - 5*x^2 - 2*x^3 + x^4)^(1/2)) / (2*x + 2*x^2) = -1 + 2*(1 + x) / (1 + x + x^2 + sqrt((1 - x + x^2)^2 - 8*x^2)).
%F G.f. A(x) satisfies A(x) = x + (x + x^2) * (A(x) + A(x)^2). - _Michael Somos_, Sep 08 2005
%F Given g.f. A(x), then series reversion of B(x) = x + x*A(x) is -B(-x). - _Michael Somos_, Sep 08 2005
%F Given g.f. A(x), then B(x) = x + x*A(x) satisfies 0 = f(x, B(x)) where f(u, v) = u^2*(v + v^2) + u*(1 + v + v^2) - v. - _Michael Somos_, Sep 08 2005
%F Given g.f. A(x), then B(x) = x + x*A(x) satisfies B(x) = x + C(x*B(x)) where C(x) is g.f. of A006318 with offset 1. - _Michael Somos_, Sep 08 2005
%F D-finite with recurrence: (n+1)*a(n) +(-n+2)*a(n-1) +(-7*n+11)*a(n-2) +(-7*n+17)*a(n-3) +(-n+2)*a(n-4) +(n-5)*a(n-5)=0. - _R. J. Mathar_, Nov 26 2012
%F a(n) = sum(k=0..n, ((sum(i=0..n-k, binomial(k+1,n-k-i)*binomial(k+i,k)))*binomial(n-k-2,k))/(k+1)), n>0, a(0)=0. - _Vladimir Kruchinin_, Nov 22 2014.
%F a(n) ~ sqrt(2 - 1/sqrt(2) + sqrt(7*(4*sqrt(2)-5)/2)) * ((1 + 2*sqrt(2) + sqrt(5 + 4*sqrt(2)))/2)^n / (2 * n^(3/2) * sqrt(Pi)). - _Vaclav Kotesovec_, Jan 27 2015
%e x + x^2 + 3*x^3 + 7*x^4 + 19*x^5 + 53*x^6 + 153*x^7 + 453*x^8 + 1367*x^9 + ...
%t CoefficientList[Series[(1 - x - x^2 - (1 - 2*x - 5*x^2 - 2*x^3 + x^4)^(1/2)) / (2*x + 2*x^2), {x, 0, 20}], x] (* _Vaclav Kotesovec_, Jan 27 2015 *)
%t CoefficientList[Series[(1 - x - x^2 - Sqrt[1 - 2 x - 5 x^2 - 2 x^3 + x^4]) / (2 x + 2 x^2), {x, 0, 33}], x] (* _Vincenzo Librandi_, May 27 2016 *)
%o (PARI) {a(n) = if( n<1, 0, polcoeff( -1 + 2*(1 + x) / (1 + x + x^2 + sqrt((1 - x + x^2)^2 - 8*x^2 + x*O(x^n))), n))} /* _Michael Somos_, Sep 08 2005 */
%o (Maxima) a(n):=if n=0 then 0 else sum(((sum(binomial(k+1,n-k-i)*binomial(k+i,k),i,0,n-k))*binomial(n-k-2,k))/(k+1),k,0,n); /* _Vladimir Kruchinin_, Nov 22 2014 */
%Y Cf. A006318, A094507.
%K nonn
%O 0,4
%A _N. J. A. Sloane_, Jan 04 2003
%E Replaced definition with g.f. given by Atkinson and Still (2002). - _N. J. A. Sloane_, May 24 2016
|
