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

0, 24, 496, 1764, 3768, 6508, 9984, 14196, 19144, 24828, 31248, 38404, 46296, 54924, 64288, 74388, 85224, 96796, 109104, 122148, 135928, 150444, 165696, 181684, 198408, 215868, 234064, 252996, 272664, 293068, 314208, 336084, 358696, 382044, 406128, 430948, 456504, 482796, 509824

Offset: 1

Author

R. H. Hardin, Feb 27 2011

Keywords

• nonn
• easy

Comments

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

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

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

[0 0 0 2]

[0 24 80 28]

[0 80 80 20]

[2 28 20 4] (End)

Examples

			Some solutions for 3 X 3:
  0 3 0   0 2 0   0 0 1   1 0 0   0 0 0   0 4 3   4 0 0
  0 2 4   0 3 1   0 0 2   4 2 0   0 1 4   0 2 1   1 3 0
  0 1 0   0 0 4   4 3 0   3 0 0   0 3 2   0 0 0   2 0 0
		

Links

• J. Volkmar Schmidt, Table of n, a(n) for n = 1..50
• Index entries for linear recurrences with constant coefficients, signature (3, -3, 1).

Crossrefs

Row 4 of A186861.

Formula

a(n) = 368*n^2 - 1308*n + 1108 = 4*(92*(n-1)*(n-3) + 41*n + 1) for n > 2.

G.f.: 4*x^2*(6 + 106*x + 87*x^2 - 15*x^3)/(1-x)^3. - Colin Barker, Jan 22 2012

Extensions

a(34)-a(39) from J. Volkmar Schmidt, Sep 03 2023