A186867 Number of 8-step king's tours on an n X n board summed over all starting positions.

0, 0, 2384, 183472, 1110000, 3193800, 6481216, 10899404, 16418600, 23038804, 30760016, 39582236, 49505464, 60529700, 72654944, 85881196, 100208456, 115636724, 132166000, 149796284, 168527576, 188359876, 209293184, 231327500, 254462824, 278699156

Offset: 1

Author

R. H. Hardin, Feb 27 2011

Keywords

• nonn

Comments

From J. Volkmar Schmidt, Oct 24 2023 (Start)

Proof of a(n) follows proof scheme from David A. Corneth for A186864.

Distribution matrix of surrounding rectangles for 8-step walks is:

[0 0 0 0 0 0 0 2]

[0 0 0 416 3264 4224 2304 508]

[0 0 2384 26004 38120 26164 10080 1764]

[0 416 26004 67424 53320 26480 8460 1328]

[0 3264 38120 53320 32032 13428 3816 560]

[0 4224 26164 26480 13428 4952 1260 172]

[0 2304 10080 8460 3816 1260 288 36]

[2 508 1764 1328 560 172 36 4]

(End)

Examples

			Some solutions for 4 X 4:
  0 7 6 0    2 1 0 8    0 0 1 0    0 0 6 8    3 4 5 0
  8 0 5 1    4 3 7 0    0 0 3 2    0 0 7 5    2 0 6 0
  0 4 3 2    0 5 6 0    0 7 5 4    2 1 4 0    1 0 7 8
  0 0 0 0    0 0 0 0    0 8 6 0    0 3 0 0    0 0 0 0
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (3, -3, 1).

Crossrefs

Row 8 of A186861.

Formula

Empirical: a(n) = 550504*n^2 - 3839372*n + 6382124 for n > 6.

Extensions

a(12)-a(26) from J. Volkmar Schmidt, Aug 27 2023