A078481 Expansion of (1 - x - x^2 - sqrt(1 - 2*x - 5*x^2 - 2*x^3 + x^4)) / (2*x + 2*x^2).
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
Offset: 0
Keywords
Examples
x + x^2 + 3*x^3 + 7*x^4 + 19*x^5 + 53*x^6 + 153*x^7 + 453*x^8 + 1367*x^9 + ...
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..1000
- 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.
Programs
-
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 *) -
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 */
-
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 */
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
Extensions
Replaced definition with g.f. given by Atkinson and Still (2002). - N. J. A. Sloane, May 24 2016
Comments