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

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