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
Examples
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).
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.