login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A078481 Expansion of (1 - x - x^2 - sqrt(1 - 2*x - 5*x^2 - 2*x^3 + x^4)) / (2*x + 2*x^2). 6
0, 1, 1, 3, 7, 19, 53, 153, 453, 1367, 4191, 13015, 40857, 129441, 413337, 1328971, 4298727, 13978971, 45673981, 149867513, 493638797, 1631616239, 5410015615, 17990076527, 59981630321, 200476419713, 671564145137, 2254338511507, 7582179238151, 25547868961315 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,4
COMMENTS
Number of irreducible stack sortable permutations of degree n.
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
From Paul Barry, Jan 29 2009: (Start)
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
1/(1+x-2x/(1+x-x/(1+x-2x/(1+x-x/(1+x-2x/(1+x-x/(1-..... (continued fraction). (End)
LINKS
Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Enumerative Aspects, 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.
Andrei Asinowski, Axel Bacher, Cyril Banderier, and Bernhard Gittenberger, Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Laboratoire d'Informatique de Paris Nord (LIPN 2019).
M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Preprint, 2002.
M. D. Atkinson and T. Stitt, Restricted permutations and the wreath product, Discrete Math., 259 (2002), 19-36.
J.-L. Baril, Avoiding patterns in irreducible permutations, Discrete Mathematics and Theoretical Computer Science, Vol 17, No 3 (2016). See Table 4.
Paul Barry, On Motzkin-Schröder Paths, Riordan Arrays, and Somos-4 Sequences, J. Int. Seq. (2023) Vol. 26, Art. 23.4.7.
Toufik Mansour, Statistics on Dyck Paths, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.
FORMULA
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)).
G.f. A(x) satisfies A(x) = x + (x + x^2) * (A(x) + A(x)^2). - Michael Somos, Sep 08 2005
Given g.f. A(x), then series reversion of B(x) = x + x*A(x) is -B(-x). - Michael Somos, Sep 08 2005
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
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
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
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.
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
EXAMPLE
x + x^2 + 3*x^3 + 7*x^4 + 19*x^5 + 53*x^6 + 153*x^7 + 453*x^8 + 1367*x^9 + ...
MATHEMATICA
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 *)
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 *)
PROG
(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 */
(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 */
CROSSREFS
Sequence in context: A026299 A183117 A183124 * A183122 A104522 A351633
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Jan 04 2003
EXTENSIONS
Replaced definition with g.f. given by Atkinson and Still (2002). - N. J. A. Sloane, May 24 2016
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 21 03:13 EST 2024. Contains 370219 sequences. (Running on oeis4.)