[seqfan] Re: Knight Tour recurrences - same as King Tour

[franktaw at netscape.net]

Probably you will only see that recurrence for pieces with only a 
finite (bounded) number of moves on any turn. I'm going to go out on a 
limb and guess that you will see a recurrence 4a(n-1) - 6a(n-2) + 
4a(n-3) - a(n-4) for pieces with unbounded moves.

Franklin T. Adams-Watters

-----Original Message-----
From: Ron Hardin <rhhardin at att.net>

Knight tour counts have the same recurrence as the king tour counts 
(row 1 of
course is automatic, but for all rows to have the same recurrence still 
seems
surprising), suggesting now a wild guess that any sort of piece-move 
will have
that same recurrence; I don't have enough numbers yet to tell.

T(n,k)=Number of n-step knight's tours on a (k+2)X(k+2) board summed 
over all
starting positions

Table starts
..9...16.....25......36......49......64......81.....100....121....144...1
69
.16...48.....96.....160.....240.....336.....448.....576....720....880..10
56
.16..104....328.....664....1112....1672....2344....3128...4024...5032..61
52
.16..208....976....2576....5056....8320...12368...17200..22816..29216.364
00
.16..400...2800....9328...21480...39616...63440...92656.127264.167264....
..
.16..800...8352...34448...91328..186544..322528..498320.712080...........
..
.16.1280..21664..118480..372384..847520.1584576.2596480..................
..
.16.2208..57392..405040.1508784.3846192.7777808..........................
..
..0.3184.135184.1290112.5807488..........................................
..
..0.4640.317296.4089632..................................................
..

Empirical, for all rows: a(n)=3*a(n-1)-3*a(n-2)+a(n-3) for 
n>3,3,4,6,8,10
respectively for row in 1..6
 rhhardin at mindspring.com
rhhardin at att.net (either)