A230122 1-Fibonacci lattice paths.

1, 1, 3, 8, 23, 67, 199, 600, 1834, 5674, 17743, 56011, 178301, 571812, 1845913, 5993985, 19565770, 64168531, 211343740, 698753053, 2318315786, 7716186315, 25757105801, 86208990248, 289253059765, 972729789813

Offset

1,3

Comments

a(n) is the number of lattice paths, never going below the x-axis, from (0,0) to (n,0) consisting of up steps U = (1,1), down steps D = (1,-1) and horizontal steps H(s) = (s,0) for every positive integer s, such that H(s) is colored by means of F(s) colors, where F(s) is the s-th Fibonacci number.

Links

Table of n, a(n) for n=1..26.

R. De Castro, A. Ramírez, and J. Ramírez, Applications in enumerative combinatorics of infinite weighted automata and graphs, arXiv:1310.2449, (2013).

Formula

G.f.: (1-2*z-z^2-sqrt((1-2*z-z^2)^2-4*z^2*(1-z-z^2)^2))/(2*z^2*(1-z-z^2)).

D-finite with recurrence: n*(n+2)*a(n) = (7*n^2 + 5*n - 1)*a(n-1) - (14*n^2 - 8*n + 1)*a(n-2) + (3*n^2 - 12*n + 23)*a(n-3) + (n+1)*(13*n - 38)*a(n-4) - 4*(n-4)*n*a(n-5) - 4*(n-5)*(n+1)*a(n-6). - Vaclav Kotesovec, Mar 15 2014

a(n) ~ sqrt(663+161*sqrt(17)) * ((3+sqrt(17))/2)^(n-3/2) / (sqrt(2*Pi) * n^(3/2)). - Vaclav Kotesovec, Mar 15 2014

Mathematica

Rest[CoefficientList[Series[(1-2*x-x^2-Sqrt[(1-2*x-x^2)^2-4*x^2*(1-x-x^2)^2])/(2*x^2*(1-x-x^2)), {x, 0, 20}], x]] (* Vaclav Kotesovec, Mar 15 2014 *)

Crossrefs

Cf. A000045.

Sequence in context: A050535 A025578 A038151 * A199103 A057198 A025262

Adjacent sequences: A230119 A230120 A230121 * A230123 A230124 A230125

Keyword

nonn

Author

José Luis Ramírez Ramírez, Oct 10 2013

Status

approved