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,3

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)

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).

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

Example

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

Mathematica

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

Prog

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

Crossrefs

Cf. A186861, A272763.

Sequence in context: A254694 A279983 A187862 * A338963 A135239 A046043

Adjacent sequences: A186861 A186862 A186863 * A186865 A186866 A186867

Keyword

nonn,easy

Author

R. H. Hardin, Feb 27 2011

Status

approved