|
|
A025250
|
|
a(n) = a(1)*a(n-1) + a(2)*a(n-2) + ...+ a(n-3)*a(3) for n >= 4.
|
|
12
|
|
|
0, 1, 1, 0, 1, 1, 1, 3, 3, 6, 11, 15, 31, 50, 85, 161, 267, 490, 883, 1548, 2863, 5127, 9307, 17116, 31021, 57123, 104963, 192699, 356643, 658034, 1218517, 2262079, 4196895, 7812028, 14549655, 27126118, 50671255, 94697293, 177220411, 332015747
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,8
|
|
COMMENTS
|
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
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (1 +x^2 -sqrt(1-2*x^2-4*x^3+x^4))/2. - Michael Somos, Jun 08 2000
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
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
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
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
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
Shifts left 3 places under the INVERT transform. - J. Conrad, Mar 08 2023
|
|
MATHEMATICA
|
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 *)
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 *)
|
|
PROG
|
(PARI) a(n)=polcoeff((x^2-sqrt(1-2*x^2-4*x^3+x^4+x*O(x^n)))/2, n)
(Haskell)
a025250 n = a025250_list !! (n-1)
a025250_list = 0 : 1 : 1 : f 1 [1, 1, 0] where
f k xs = x' : f (k+1) (x':xs) where
x' = sum $ zipWith (*) a025250_list $ take k xs
(Maxima)
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 */
(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
(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
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|