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

[franktaw at netscape.net]

x^6-4*x^5+5*x^4-5*x^2+4*x-1 = (x-1)^5 * (x+1), so in these cases there 
is a (-1)^n term.  This is a bit surprising, but not terribly so.

By the way, check out http://en.wikipedia.org/wiki/Fairy_chess_piece; 
most of these non-standard chess pieces have names.

Franklin T. Adams-Watters

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

Quick computation of all the 3-move tours for various pieces in the job 
queue
gives (with a surprise)

  16 104 328 664 1112 1672 2344 3128 4024 5032 6152 7384 8728 10184 
11752 13432
15224 17128 19144 21272 23512 25864 28328 30904 33592 36392
Number of 3-step knight's tours on a (n+2)X(n+2) board summed over all 
starting
positions
Empirical: a(n)=3*a(n-1)-3*a(n-2)+a(n-3) for n>4

  0 24 160 408 768 1240 1824 2520 3328 4248 5280 6424 7680 9048 10528 
12120 13824

15640 17568 19608 21760 24024 26400 28888 31488 34200 37024 39960
Number of 3-step king's tours on a nXn board summed over all starting 
positions
Empirical: a(n)=3*a(n-1)-3*a(n-2)+a(n-3)

 0 8 44 104 188 296 428 584 764 968 1196 1448 1724 2024 2348
Number of 3-step one space at a time rook's tours on a nXn board summed 
over all

starting positions
Empirical: a(n)=3*a(n-1)-3*a(n-2)+a(n-3) for n>4

  0 8 108 480 1400 3240 6468 11648 19440 30600 45980 66528 93288 127400 
170100
222720 286688
Number of 3-turn rook's tours on a nXn board summed over all starting 
positions
Empirical: a(n)=5*a(n-1)-10*a(n-2)+10*a(n-3)-5*a(n-4)+a(n-5)

  0 24 296 1304 3808 8832 17672 31888 53312 84040 126440 183144 257056 
351344
469448
Number of 3-turn queen's tours on a nXn board summed over all starting 
positions
Empirical: a(n)=4*a(n-1)-5*a(n-2)+5*a(n-4)-4*a(n-5)+a(n-6)

 0 0 28 152 488 1192 2468 4560 7760 12400 18860 27560 38968 53592 71988
Number of 3-turn bishop's tours on a nXn board summed over all starting
positions
Empirical: a(n)=4*a(n-1)-5*a(n-2)+5*a(n-4)-4*a(n-5)+a(n-6)

 0 0 20 64 132 224 340 480 644 832 1044 1280 1540 1824 2132
Number of 3-step one space at a time bishop's tours on a nXn board 
summed over
all starting positions
Empirical: a(n)=3*a(n-1)-3*a(n-2)+a(n-3) for n>4

The 1 4 5 0 5 4 1 pair is a surprise.  So much for my polynomial 
conjecture.

 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/
>

_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/