[seqfan] Re: Knight Tour recurrences - same as King Tour
Ron Hardin
rhhardin at att.net
Sat Feb 26 00:28:28 CET 2011
Taking the rook out of order from the job queue, row 3 (number of 3-move tours)
obeys
Empirical: a(n)=5*a(n-1)-10*a(n-2)+10*a(n-3)-5*a(n-4)+a(n-5)
(for unrestricted n).
It just occurs to me that these recurrences are from m'th differences being
zero, ie that a(n) is eventually a polynomial in n, which perhaps is then less
surprising to me.
rhhardin at mindspring.com
rhhardin at att.net (either)
----- Original Message ----
> From: "franktaw at netscape.net" <franktaw at netscape.net>
> To: seqfan at list.seqfan.eu
> Sent: Fri, February 25, 2011 5:19:37 PM
> Subject: [seqfan] Re: Knight Tour recurrences - same as King Tour
>
> 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)
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list