A006191 Number of paths on square lattice.

1, 2, 5, 16, 54, 180, 595, 1964, 6485, 21418, 70740, 233640, 771661, 2548622, 8417525, 27801196, 91821114, 303264540, 1001614735, 3308108744, 10925940965, 36085931638, 119183735880, 393637139280, 1300095153721, 4293922600442

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• walk
• easy

References

• H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..1928
• H. L. Abbott and D. Hanson, A lattice path problem, Ars Combin., 6 (1978), 163-178. (Annotated scanned copy)
• Index entries for linear recurrences with constant coefficients, signature (4,-3,2,1).

Programs

Mathematica

LinearRecurrence[{4,-3,2,1},{1,2,5,16},30] (* Harvey P. Dale, Mar 22 2018 *)

Formula

a(n) = 1 + Sum_{k=1..n-1} A006189(k). - Sean A. Irvine, Jan 20 2017

From Colin Barker, Jan 20 2017: (Start)

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

G.f.: x*(1 - 2*x) / ((1 - x + x^2)*(1 - 3*x - x^2)).

(End)

Extensions

Offset corrected and more terms from Sean A. Irvine, Jan 20 2017