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

Author

J. Volkmar Schmidt, Oct 25 2023

Keywords

• nonn
• easy
• walk

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]

Examples

			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
		

Links

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

Crossrefs

Row 9 of A186861.

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