login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A186864 Number of 5-step king's tours on an n X n board summed over all starting positions. 7
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 (list; graph; refs; listen; history; text; internal format)
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)
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
Sequence in context: A254694 A279983 A187862 * A338963 A135239 A046043
KEYWORD
nonn,easy
AUTHOR
R. H. Hardin, Feb 27 2011
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 13 04:46 EDT 2024. Contains 374267 sequences. (Running on oeis4.)