OFFSET
0,3
COMMENTS
G.f. A(x) satisfies A(x)^2 + A(x) = (x^2 + x)/(1 - 4*x - 4*x^2). - Michael Somos, Jan 28 2019
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000
M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv:1410.5747 [math.CO], 2014.
FORMULA
G.f.: (1/2)*(-1 + 1/sqrt(1 - 4*x - 4*x^2)).
a(n) = Sum_{m=1..n} m*Sum_{k=m..n} Sum_{i=k..n} binomial(i-1,k-1)* binomial(i,n-i))*Sum_{j=0..k} binomial(j,2*j-m-k)*binomial(k,j))/k)). - Vladimir Kruchinin, Mar 11 2011
a(n) = Sum_{k=0..n} 2^(n-k-1)*binomial(n,k)*binomial(n-k,k). - Vladimir Kruchinin, Mar 12 2015
From Vaclav Kotesovec, Jan 26 2019: (Start)
D-finite with recurrence: n*a(n) = 2*(2*n - 1)*a(n-1) + 4*(n-1)*a(n-2).
a(n) ~ 2^(n - 7/4) * (1 + sqrt(2))^(n + 1/2) / sqrt(Pi*n). (End)
0 = a(n)*(16*a(n+1) +24*a(n+2) -8*a(n+3)) + a(n+1)*(+8*a(n+1) +16*a(n+2) -6*a(n+3)) + a(n+2)*(-2*a(n+2) +a(n+3)) for all n in Z except n=-1. - Michael Somos, Jan 27 2019
a(n) = A006139(n)/2, n>0. - R. J. Mathar, Jan 24 2020
EXAMPLE
G.f. = x + 4*x^2 + 16*x^3 + 68*x^4 + 296*x^5 + 1312*x^6 + 5888*x^7 + ....
MATHEMATICA
CoefficientList[1/2 (-1 + (1-4x-4x^2)^(-1/2)) + O[x]^23, x] (* Jean-François Alcover, Jul 27 2018 *)
PROG
(Maxima)
a(n):=sum(m*sum(sum(binomial(i-1, k-1)*binomial(i, n-i), i, k, n)*sum(binomial(j, 2*j-m-k)*binomial(k, j), j, 0, k)/k, k, m, n), m, 1, n); /* Vladimir Kruchinin, Mar 11 2011 */
a(n):=sum(2^(n-k-1)*binomial(n, k)*binomial(n-k, k), k, 0, n); /* Vladimir Kruchinin, Mar 12 2015 */
(PARI) my(x='x+O('x^30)); concat([0], Vec((-1 +1/sqrt(1-4*x-4*x^2))/2)) \\ G. C. Greubel, Jan 25 2019
(Magma) m:=30; R<x>:=PowerSeriesRing(Rationals(), m); Coefficients(R!( (-1 + 1/Sqrt(1-4*x-4*x^2))/2 )); // G. C. Greubel, Jan 25 2019
(Sage) ((-1 + 1/sqrt(1-4*x-4*x^2))/2).series(x, 20).coefficients(x, sparse=False) # G. C. Greubel, Jan 25 2019
CROSSREFS
KEYWORD
nonn
AUTHOR
Clark Kimberling, Jul 01 2010
STATUS
approved