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

%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