A089324 Number of lattice paths from (0,0) to the line x+y=n that use the step set {(0,1),(1,0),(2,0),(3,0),...} and never pass below y=x.

1, 1, 2, 3, 7, 12, 29, 53, 130, 247, 611, 1192, 2965, 5897, 14726, 29723, 74443, 152020, 381617, 786733, 1978582, 4111295, 10355303, 21661168, 54628201, 114925697, 290148890, 613442227, 1550177791, 3291704108, 8324934533, 17745496453

Offset

0,3

Comments

a(n) = Sum(A011117(i,n-i), i=0..floor(n/2)), i.e. diagonal sums in A011117 formatted as an upper right triangle.

Hankel transform is A060656. - Paul Barry, Mar 01 2010

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Formula

G.f.: 2/[(1-z)^2+sqrt(1-6z^2+z^4)].

G.f.: 1/(1-x-x^2/(1-2x^2/(1-x^2/(1-2x^2/(1-x^2/(1-2x^2/(1-... (continued fraction). - Paul Barry, Mar 01 2010

Conjecture: (n+1)*a(n) +3*(-n-1)*a(n-1) +(-5*n+13)*a(n-2) +18*(n-2)*a(n-3) +(-5*n+7)*a(n-4) +3*(-n+5)*a(n-5) +(n-5)*a(n-6)=0. - R. J. Mathar, Nov 24 2012

a(n) ~ sqrt(6*sqrt(2)-8) * (1 - (12*sqrt(2)-17)*(-1)^n) * (sqrt(2)+1)^(n+4) / (2 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 09 2014

Example

a(4) = 7 because we have VVVV, VVVh, VVhV, VhVV, VVH, VVhh and VhVh, where V=(0,1), h=(1,0) and H=(2,0).

Mathematica

CoefficientList[Series[2/((1-x)^2+Sqrt[1-6*x^2+x^4]), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 09 2014 *)

Crossrefs

Cf. A011117.

Sequence in context: A342132 A032173 A130616 * A339159 A297438 A111759

Adjacent sequences: A089321 A089322 A089323 * A089325 A089326 A089327

Keyword

nonn

Author

Emeric Deutsch, Dec 25 2003

Status

approved