A338426 - OEIS

A338426

a(n) is the number of paths a chess king can take from (0,0) to (n+1,0) touching each point in {-1,0,1} X {1,2,...,n} exactly once.

1, 2, 28, 154, 1206, 8364, 60614, 432636, 3104484, 22235310, 159360540, 1141875800, 8182608226, 58634396372, 420162632840, 3010793013534, 21574706493988, 154599722419136, 1107828637412194, 7938463325113516, 56885333141857872, 407628148378295190

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

LINKS

Peter Kagey, Table of n, a(n) for n = 0..1000

Code Golf Stack Exchange user Bubbler, Counting King's Hamiltonian Paths through 3-by-N grid

FORMULA

a(n) = 7*a(n-1) + 6*a(n-2) - 39*a(n-3) + 29*a(n-4) + 28*a(n-5) - 26*a(n-6) - 10*a(n-7) + 6*a(n-8) for n >= 8.

EXAMPLE

For n = 1, the a(1) = 2 paths are (0,0)->(1,1)->(1,0)->(1,-1)->(2,0) and (0,0)->(1,-1)->(1,0)->(1,1)->(2,0).

An example of one of the a(2) = 28 paths is (0,0)->(1,1)->(2,1)->(2,0)->(1,-1)->(1,0)->(2,-1)->(3,0).

CROSSREFS

Cf. A140518, A158651, A193168, A272445.

Sequence in context: A164834 A174707 A110241 * A347602 A006332 A280120

Adjacent sequences: A338423 A338424 A338425 * A338427 A338428 A338429

KEYWORD

nonn,walk

AUTHOR

Peter Kagey, Oct 25 2020

STATUS

approved