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

0, 0, 1208, 6712, 17280, 32520, 52432, 77016, 106272, 140200, 178800, 222072, 270016, 322632, 379920, 441880, 508512, 579816, 655792, 736440, 821760, 911752, 1006416, 1105752, 1209760, 1318440, 1431792, 1549816, 1672512, 1799880, 1931920

Offset: 1

Author

R. H. Hardin, Feb 27 2011

Keywords

• nonn
• easy

Comments

Row 5 of A186861.

From David A. Corneth, Sep 04 2023: (Start)

Proof of a(n) = 2336*n^2 - 10456*n + 11160 for n > 3.

For any walk we can find the surrounding rectangle it fits in.

For example, the walk

0 1 2

0 3 5

0 4 0

has width 2 and height 3.

So it fits max(0, (5 - 2 + 1))*max(0, (5 - 3 + 1)) times in a 5 X 5 grid. This way we can set up a matrix m for all possible walks where element m(r, k) is the number of walks with dimensions (r, k).

That matrix is as follows:

[0 0 0 0 2]

[0 0 160 192 60]

[0 160 568 312 72]

[0 192 312 120 24]

[2 60 72 24 4]

To find a(n) by iterating over this matrix we can compute Sum_{r=1..min(n, 5)} Sum_{k=1..min(n, 5)} m(r, k)*(n - r + 1)*(n - k + 1). This is the sum of 25 quadratics and gives the stated quadratic which completes the proof. (End)

Examples

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

Links

• David A. Corneth, Table of n, a(n) for n = 1..10000 (terms 1..32 from R. H. Hardin, terms 33..50 from J. Volkmar Schmidt)
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Crossrefs

Cf. A186861, A272763.

Programs

Mathematica

LinearRecurrence[{3,-3,1},{0,0,1208,6712,17280,32520},50] (* Paolo Xausa, Oct 29 2023 *)

PARI

a(n) = if(n <= 3, [0, 0, 1608][n], 2336*n^2 - 10456*n + 11160) \\ David A. Corneth, Sep 04 2023

Formula

Empirical: a(n) = 2336*n^2 - 10456*n + 11160 = 8*(292*(n-1)*(n-4) + 153*n + 227) for n > 3. [Proved, see comments. - David A. Corneth, Sep 04 2023]

Conjectures from Colin Barker, Apr 19 2018: (Start)

G.f.: 8*x^3*(151 + 386*x + 96*x^2 - 49*x^3) / (1 - x)^3.

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 6. (End)

The above conjectures are true. - Stefano Spezia, Oct 28 2023