OFFSET
1,2
COMMENTS
Simple paths are self-avoiding walks.
Note: Number of paths from (1, 1) to (n, 2) on a n X 2 grid matches the sequence A086347.
Example: a(2) = 24 paths from (1, 1) to (2, 3)
1 [(1, 1), (2, 1), (1, 2), (1, 3), (2, 3)]
2 [(1, 1), (2, 2), (1, 3), (2, 3)]
3 [(1, 1), (2, 2), (2, 1), (1, 2), (2, 3)]
4 [(1, 1), (1, 2), (2, 1), (2, 2), (1, 3), (2, 3)]
5 [(1, 1), (2, 2), (2, 1), (1, 2), (1, 3), (2, 3)]
6 [(1, 1), (1, 2), (2, 2), (1, 3), (2, 3)]
7 [(1, 1), (1, 2), (1, 3), (2, 3)]
8 [(1, 1), (2, 2), (1, 3), (1, 2), (2, 3)]
9 [(1, 1), (2, 2), (2, 3)]
10 [(1, 1), (1, 2), (2, 3)]
11 [(1, 1), (2, 2), (1, 2), (1, 3), (2, 3)]
12 [(1, 1), (2, 1), (2, 2), (1, 3), (2, 3)]
13 [(1, 1), (2, 1), (2, 2), (1, 2), (2, 3)]
14 [(1, 1), (2, 1), (1, 2), (1, 3), (2, 2), (2, 3)]
15 [(1, 1), (1, 2), (2, 1), (2, 2), (2, 3)]
16 [(1, 1), (2, 1), (2, 2), (1, 3), (1, 2), (2, 3)]
17 [(1, 1), (2, 1), (1, 2), (2, 3)]
18 [(1, 1), (1, 2), (2, 2), (2, 3)]
19 [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3)]
20 [(1, 1), (2, 1), (2, 2), (1, 2), (1, 3), (2, 3)]
21 [(1, 1), (2, 2), (1, 2), (2, 3)]
22 [(1, 1), (2, 1), (2, 2), (2, 3)]
23 [(1, 1), (2, 1), (1, 2), (2, 2), (2, 3)]
24 [(1, 1), (2, 1), (1, 2), (2, 2), (1, 3), (2, 3)]
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..200
FORMULA
Conjectures from Andrew Howroyd, Nov 05 2019: (Start)
a(n) = 12*a(n-1) + 6*a(n-2) + 50*a(n-3) + 300*a(n-4) - 194*a(n-5) - 833*a(n-6) + 352*a(n-7) + 661*a(n-8) - 84*a(n-9) - 219*a(n-10) + 72*a(n-11) + 54*a(n-12) for n > 12.
G.f.: x*(1 + 12*x - 59*x^2 - 92*x^3 + 195*x^4 + 280*x^5 + 102*x^6 - 178*x^7 - 67*x^8 + 109*x^9 - 75*x^10 - 54*x^11)/((1 + x + 9*x^2 + 24*x^3 + 9*x^4)*(1 - 13*x - 2*x^2 + 45*x^3 - 24*x^4 - 22*x^5 + 9*x^6 + 8*x^7 - 6*x^8)).
(End)
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Matías Benzo, Jul 17 2011
EXTENSIONS
Offset changed and more terms from Andrew Howroyd, Nov 05 2019
STATUS
approved