A366829 Number of 9-step self-avoiding king's tours on an n X n board summed over all starting positions.

0, 0, 784, 436984, 3908376, 13530576, 30543072, 54738536, 85743256, 123447704, 167851880, 218955784, 276759416, 341262776, 412465864, 490368680, 574971224, 666273496, 764275496, 868977224, 980378680, 1098479864, 1223280776, 1354781416, 1492981784, 1637881880

Offset

1,3

Comments

Proof of the formula follows proof scheme from David A. Corneth for A186864.

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

[0 0 0 0 0 0 0 0 2]

[0 0 0 0 3584 10496 10752 5120 1020]

[0 0 784 43856 129100 136320 83208 29160 4680]

[0 0 43856 258424 318816 215096 99984 29680 4296]

[0 3584 129100 318816 262816 142888 57376 15400 2100]

[0 10496 136320 215096 142888 67688 24288 5960 768]

[0 10752 83208 99984 57376 24288 7864 1760 212]

[0 5120 29160 29680 15400 5960 1760 360 40]

[2 1020 4680 4296 2100 768 212 40 4]

Links

Table of n, a(n) for n=1..26.

Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Formula

a(n) = 3349864*n^2 - 25942968*n + 47890984 for n>7.

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 10. - Stefano Spezia, Oct 28 2023

Example

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

Crossrefs

Row 9 of A186861.

Sequence in context: A184601 A151658 A231771 * A252389 A159896 A031734

Adjacent sequences: A366826 A366827 A366828 * A366830 A366831 A366832

Keyword

nonn,easy,walk

Author

J. Volkmar Schmidt, Oct 25 2023

Status

approved