login
a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ...+ a(n-3)*a(3) for n >= 4.
12

%I #56 Mar 10 2023 19:19:34

%S 0,1,1,0,1,1,1,3,3,6,11,15,31,50,85,161,267,490,883,1548,2863,5127,

%T 9307,17116,31021,57123,104963,192699,356643,658034,1218517,2262079,

%U 4196895,7812028,14549655,27126118,50671255,94697293,177220411,332015747

%N a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ...+ a(n-3)*a(3) for n >= 4.

%C Number of lattice paths from (0,0) to (n-3,0) that stay weakly in the first quadrant and such that each step is either U=(1,1),D=(2,-1), or H=(2,0). E.g. a(10)=6 because we have HHUD, HUDH, HUHD, UDHH, UHDH and UHHD. - _Emeric Deutsch_, Dec 23 2003

%C Hankel transform of a(n+2) is Somos-4 variant A050512. - _Paul Barry_, Jul 05 2009

%H Reinhard Zumkeller, <a href="/A025250/b025250.txt">Table of n, a(n) for n = 1..1000</a>

%H Andrei Asinowski, Cyril Banderier, and Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, (2019).

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Barry/barry321.html">Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices</a>, Journal of Integer Sequences, 19, 2016, #16.3.5.

%H Paul Barry, <a href="https://arxiv.org/abs/1807.05794">Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences</a>, arXiv:1807.05794 [math.CO], 2018.

%F G.f.: (1 +x^2 -sqrt(1-2*x^2-4*x^3+x^4))/2. - _Michael Somos_, Jun 08 2000

%F G.f.: x^2+x^3*(1/(1-x^2))c(x^3/(1-x^2)^2) where c(x) is the g.f. of A000108. - _Paul Barry_, May 20 2009

%F a(n+2) = Sum_{k=0..n} binomial((n+k)/2, 2*k)(1+(-1)^(n-k))*A000108(k)/2}. - _Paul Barry_, Jul 06 2009

%F a(n) = Sum_{k=0..n} binomial(k+1,n-2*k-1)*binomial(n-k-2,k)/(k+1). - _Vladimir Kruchinin_, Nov 22 2014

%F G.f.: K_{k>=0} (-x^3)/(x^2-1), where K is the Gauss notation for a continued fraction. - _Benedict W. J. Irwin_, Oct 11 2016

%F a(n) ~ sqrt(1 - r^2 - r^3) * (2*r + 4*r^2 - r^3)^n / (2*sqrt(Pi)*n^(3/2)), where r = 0.51361982956383128341133963576515885989214886200017191578885... is the root of the equation 1 - 2*r^2 - 4*r^3 + r^4 = 0. - _Vaclav Kotesovec_, Jul 03 2021

%F Shifts left 3 places under the INVERT transform. - _J. Conrad_, Mar 08 2023

%t Rest[CoefficientList[Series[(1+x^2-Sqrt[1-2*x^2-4*x^3+x^4])/2, {x,0,40}],x]] (* _Harvey P. Dale_, Apr 05 2011 *)

%t Rest@CoefficientList[Series[x^2+ContinuedFractionK[-x^3,x^2-1,{k, 0, 40}],{x,0,40}], x] (* _Benedict W. J. Irwin_, Oct 13 2016 *)

%o (PARI) a(n)=polcoeff((x^2-sqrt(1-2*x^2-4*x^3+x^4+x*O(x^n)))/2,n)

%o (Haskell)

%o a025250 n = a025250_list !! (n-1)

%o a025250_list = 0 : 1 : 1 : f 1 [1,1,0] where

%o f k xs = x' : f (k+1) (x':xs) where

%o x' = sum $ zipWith (*) a025250_list $ take k xs

%o -- _Reinhard Zumkeller_, Nov 03 2011

%o (Maxima)

%o a(n):=sum((binomial(k+1,n-2*k-1)*binomial(n-k-2,k))/(k+1),k,0,n); /* _Vladimir Kruchinin_, Nov 22 2014 */

%o (Magma) m:=45; R<x>:=PowerSeriesRing(Rationals(), m); [0] cat Coefficients(R!( (1 +x^2 -Sqrt(1-2*x^2-4*x^3+x^4))/2 )); // _G. C. Greubel_, Feb 23 2019

%o (Sage) a=((1+x^2 -sqrt(1-2*x^2-4*x^3+x^4))/2).series(x, 45).coefficients(x, sparse=False); a[1:] # _G. C. Greubel_, Feb 23 2019

%o (GAP) List([0..45], n-> Sum([0..n], k-> binomial(k+1,n-2*k-1)*binomial(n-k-2,k)/(k+1) )) # _G. C. Greubel_, Feb 23 2019

%K nonn

%O 1,8

%A _Clark Kimberling_