%I #69 Jan 17 2024 09:12:13
%S 0,0,1208,6712,17280,32520,52432,77016,106272,140200,178800,222072,
%T 270016,322632,379920,441880,508512,579816,655792,736440,821760,
%U 911752,1006416,1105752,1209760,1318440,1431792,1549816,1672512,1799880,1931920
%N Number of 5-step king's tours on an n X n board summed over all starting positions.
%C Row 5 of A186861.
%C From _David A. Corneth_, Sep 04 2023: (Start)
%C Proof of a(n) = 2336*n^2 - 10456*n + 11160 for n > 3.
%C For any walk we can find the surrounding rectangle it fits in.
%C For example, the walk
%C 0 1 2
%C 0 3 5
%C 0 4 0
%C has width 2 and height 3.
%C 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).
%C That matrix is as follows:
%C [0 0 0 0 2]
%C [0 0 160 192 60]
%C [0 160 568 312 72]
%C [0 192 312 120 24]
%C [2 60 72 24 4]
%C 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)
%H David A. Corneth, <a href="/A186864/b186864.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..32 from R. H. Hardin, terms 33..50 from J. Volkmar Schmidt)
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).
%F 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]
%F Conjectures from _Colin Barker_, Apr 19 2018: (Start)
%F G.f.: 8*x^3*(151 + 386*x + 96*x^2 - 49*x^3) / (1 - x)^3.
%F a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 6. (End)
%F The above conjectures are true. - _Stefano Spezia_, Oct 28 2023
%e Some solutions for 3 X 3:
%e 0 5 0 0 1 2 3 1 0 3 2 1 0 1 2 0 1 2 0 5 0
%e 2 3 4 0 3 5 2 4 0 5 4 0 0 4 3 0 5 3 1 3 4
%e 1 0 0 0 4 0 5 0 0 0 0 0 0 5 0 0 0 4 2 0 0
%t LinearRecurrence[{3,-3,1},{0,0,1208,6712,17280,32520},50] (* _Paolo Xausa_, Oct 29 2023 *)
%o (PARI) a(n) = if(n <= 3, [0, 0, 1608][n], 2336*n^2 - 10456*n + 11160) \\ _David A. Corneth_, Sep 04 2023
%Y Cf. A186861, A272763.
%K nonn,easy
%O 1,3
%A _R. H. Hardin_, Feb 27 2011