A169764 -id:A169764 - cp's OEIS frontend

A169696 Number of undirected Knight's tours on a 3 X n board.

0, 0, 0, 8, 0, 0, 52, 396, 560, 3048, 10672, 57248, 128864, 646272, 1838784, 8636880, 23400992, 105865688, 305753680, 1322849752, 3862974304, 16225820000, 48744080192, 198673312880, 607041217056, 2417584484232, 7519864632928, 29320809649000, 92507134938336

Offset: 1

N. J. A. Sloane, Apr 14 2010, based on a communication from Don Knuth

nonn

I think the (old) name "Number of open Knight's tours on a 3 X n board" is somewhat incorrect, because included are those tours in which the start/end cells are knight-neighbors. Such tours are potentially closed, although actually closing them would deprive them of specific start/end cells. "Number of undirected Knight's tours on a 3 X n board" would be a better name. For example the 3x10 has 3048 undirected tours, which would be 6096 directed tours, in accord with Colin Rose results (http://www.tri.org.au/knightframe.html, Solutions:3xm). Note that the 3x10 also has 16 closed tours (A169764 Number of closed Knight's tours on a 3 X n board), and each of those closed tour appears 30 times among the 3048 undirected tours, and 60 times among the 6096 directed tours. - Pierre Charland, Feb 15 2011

D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.

Seiichi Manyama, Table of n, a(n) for n = 1..1861
George Jelliss, Open knight's tours of three-rank boards, Knight's Tour Notes, note 3a (21 October 2000).
George Jelliss, Closed knight's tours of three-rank boards, Knight's Tour Notes, note 3b (21 October 2000).
D. E. Knuth, Comments, generating function, first 100 terms

Cf. A118067.

a(n) = A169770(n) + A169771(n) + A169772(n).

Asymptotic value: 0.02789*3.45059^n.

A070030 Number of closed Knight's tours on a 3 X 2n board.

Original entry on oeis.org

0, 0, 0, 0, 16, 176, 1536, 15424, 147728, 1448416, 14060048, 136947616, 1332257856, 12965578752, 126169362176, 1227776129152, 11947846468608, 116266505653888, 1131418872918784, 11010065269439104, 107141489725900544, 1042616896632882688, 10145938076107491328

Offset: 1

Noam D. Elkies, Apr 13 2002

Leonhard Euler stated that no such tours are possible [Memoires Acad. Roy. Sci. (Berlin, 1759), 310-337], and many authors echoed this statement until Ernest Bergholt exhibited solutions for 2n=10 and 12 in British Chess Magazine 1918, page 74. The full set of 16 solutions for 2n=10 was published by Kraitchik in 1927. - Don Knuth, Apr 28 2010
Obtained independently by Don Knuth and Noam D. Elkies in April 1994, both using the transfer-matrix method (in slightly different ways). For this method, see for instance chapter 4.7 of R. P. Stanley's Enumerative Combinatorics, Vol. 1 (1986).
Ian Stewart, Mathematical Recreations column, Scientific American, February 1998, "Feedback", page 95, reports that Richard Ulmer of Denver has sent him a letter reporting work on this subject, about which he is writing a thesis, giving the terms though a(21). - N. J. A. Sloane, Mar 01 2018

			The smallest 3 X 2n board admitting a closed Knight's tour is the 3 X 10, on which there are 16 such tours.

D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
N. D. Elkies and R. P. Stanley, The mathematical knight, Math. Intelligencer, 25 (No. 1) (2003), 22-34.
George Jelliss, Open knight's tours of three-rank boards, Knight's Tour Notes, note 3a (21 October 2000).
George Jelliss, Closed knight's tours of three-rank boards, Knight's Tour Notes, note 3b (21 October 2000).
Eric Weisstein's World of Mathematics, Knight's Tour

See also A169764, which gives the number of closed Knight's tours on a 3 X n board. Cf. A169696, A169765-A169777, A001230.

Cf. A158074, A383660.

Rest[CoefficientList[Series[16 * (x^5 + 5*x^6 - 34*x^7 - 116*x^8 + 505*x^9 + 616*x^10 - 3179*x^11 - 4*x^12 + 9536*x^13 - 8176*x^14 - 13392*x^15 + 15360*x^16 + 13888*x^17 + 2784*x^18 - 3328*x^19 - 22016*x^20 + 5120*x^21 + 2048*x^22) / (1 - 6*x - 64*x^2 + 200*x^3 + 1000*x^4 - 3016*x^5 - 3488*x^6 + 24256*x^7 - 23776*x^8 - 104168*x^9 + 203408*x^10 + 184704*x^11 - 443392*x^12 - 14336*x^13 + 151296*x^14 - 145920*x^15 + 263424*x^16 - 317440*x^17 - 36864*x^18 + 966656*x^19 - 573440*x^20 - 131072*x^21), {x, 0, 30}], x]] (* Vaclav Kotesovec, Mar 03 2016 *)

g = 16 * (z^5 + 5*z^6 - 34*z^7 - 116*z^8 + 505*z^9 + 616*z^10 - 3179*z^11 - 4*z^ 12 + 9536*z^13 - 8176*z^14 - 13392*z^15 + 15360*z^16 + 13888*z^17 + 2784*z^18 - 3328*z^19 - 22016*z^20 + 5120*z^21 + 2048*z^22) / (1 - 6*z - 64*z^2 + 200*z^3 + 1000*z^4 - 3016*z^5 - 3488*z^6 + 24256*z^7 - 23776*z^8 - 104168*z^9 + 203408*z^1 0 + 184704*z^11 - 443392*z^12 - 14336*z^13 + 151296*z^14 - 145920*z^15 + 263424* z^16 - 317440*z^17 - 36864*z^18 + 966656*z^19 - 573440*z^20 - 131072*z^21); g = g + O(z^31); vector(30,n,polcoeff(g,n))

Generating function: 16 * (z^5 + 5*z^6 - 34*z^7 - 116*z^8 + 505*z^9 + 616*z^10 - 3179*z^11 - 4*z^12 + 9536*z^13 - 8176*z^14 - 13392*z^15 + 15360*z^16 + 13888*z^17 + 2784*z^18 - 3328*z^19 - 22016*z^20 + 5120*z^21 + 2048*z^22) / (1 - 6*z - 64*z^2 + 200*z^3 + 1000*z^4 - 3016*z^5 - 3488*z^6 + 24256*z^7 - 23776*z^8 - 104168*z^9 + 203408*z^10 + 184704*z^11 - 443392*z^12 - 14336*z^13 + 151296*z^14 - 145920*z^15 + 263424*z^16 - 317440*z^17 - 36864*z^18 + 966656*z^19 - 573440*z^20 - 131072*z^21).
Asymptotic value .0001899*3.11949^(2n). - Don Knuth, Apr 28 2010. More decimal places: a(n) ~ 0.0001898644879979384968655648993009439045986223511152141689341... * 3.1194904567551021585814810124470909514449088706168023079811958...^(2*n). - Vaclav Kotesovec, Mar 03 2016
a(n) = A158074(n)/2. - Eric W. Weisstein, Mar 18 2009
Recurrence (D. E. Knuth and N. D. Elkies, 1994): a(n) = 6*a(n-1) + 64*a(n-2) - 200*a(n-3) - 1000*a(n-4) + 3016*a(n-5) + 3488*a(n-6) - 24256*a(n-7) + 23776*a(n-8) + 104168*a(n-9) - 203408*a(n-10) - 184704*a(n-11) + 443392*a(n-12) + 14336*a(n-13) - 151296*a(n-14) + 145920*a(n-15) - 263424*a(n-16) + 317440*a(n-17) + 36864*a(n-18) - 966656*a(n-19) + 573440*a(n-20) + 131072*a(n-21), for n>=23. - Vaclav Kotesovec, Mar 03 2016
a(n) = A383660(3n). - Don Knuth, May 05 2025

Comment corrected by Johannes W. Meijer, Nov 22 2010

A169777 Number of geometrically distinct open knight's tours of a 3 X n chessboard.

Original entry on oeis.org

3, 0, 0, 14, 104, 146, 773, 2698, 14350, 32296, 161714, 460022, 2159794, 5851548, 26468357, 76442996, 330719293, 965759972, 4056479056, 12186078360, 49668414086, 151760518296, 604396415979, 1879966906486, 7330203447133, 23126786408904, 88609897281582

Offset: 4

N. J. A. Sloane, May 10 2010, based on a communication from Don Knuth, Apr 28 2010

nonn

			The three distinct 3x4 tours were published by Euler in Memoires Acad. Roy. Sci. (Berlin, 1759), 310-337.

D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.

George Jelliss, Open knight's tours of three-rank boards, Knight's Tour Notes, note 3a (21 October 2000).
George Jelliss, Closed knight's tours of three-rank boards, Knight's Tour Notes, note 3b (21 October 2000).
D. E. Knuth Generating functions for A169770-A169777 and A169696.

Cf. A070030, A169696, A169764-A169777.

a(n) = A169696(n)/4 + A169776(n)/2.

A169770 Number of open knight's tour diagrams of a 3 X n chessboard that have "type X": both endpoints occur in the same column.

Original entry on oeis.org

4, 0, 0, 0, 80, 40, 368, 352, 5296, 3744, 48656, 40208, 523808, 415488, 5270976, 4333504, 54215264, 44497728, 551297184, 458337984, 5613555008, 4691821600, 56981627840, 47988689152, 577641089664, 489273948160, 5845628996352

Offset: 4

N. J. A. Sloane, May 10 2010, based on a communication from Don Knuth, Apr 28 2010

nonn

D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.

Seiichi Manyama, Table of n, a(n) for n = 4..1000
George Jelliss, Open knight's tours of three-rank boards, Knight's Tour Notes, note 3a (21 October 2000).
George Jelliss, Closed knight's tours of three-rank boards, Knight's Tour Notes, note 3b (21 October 2000).
D. E. Knuth Generating functions for A169770-A169777 and A169696.

Cf. A070030, A169696, A169764-A169777.

Asymptotic value 0.000169*n*3.11949^n when n is even, 0.0000526*n*3.11949^n when n is odd.

A169765 Number of closed knight's tour diagrams of a 3 X n chessboard that are symmetric with respect to left-right reflection about a vertical axis.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 24, 0, 0, 0, 276, 0, 0, 0, 2604, 0, 0, 0, 25736, 0, 0, 0, 248816, 0, 0, 0, 2424608, 0, 0, 0, 23581056, 0, 0, 0, 229513584, 0, 0, 0, 2233386048, 0, 0, 0, 21733496960, 0, 0, 0, 211495383968, 0, 0, 0, 2058092298080

Offset: 4

N. J. A. Sloane, May 10 2010, based on a communication from Don Knuth, Apr 28 2010

nonn

			The first example, for n=10, was exhibited by Ernest Bergholt in British Chess Magazine 1918, page 74.

D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.

Seiichi Manyama, Table of n, a(n) for n = 4..4057 (terms 4..1002 from Alois P. Heinz)
George Jelliss, Open knight's tours of three-rank boards, Knight's Tour Notes, note 3a (21 October 2000).
George Jelliss, Closed knight's tours of three-rank boards, Knight's Tour Notes, note 3b (21 October 2000).

Cf. A070030, A169696, A169764-A169777.

A169765(n)=0 unless n mod 4 = 2. And if n mod = 2, A169765(n) = A169765(n) + A169767(n).
Generating function: (2*(2*z^10 - 62*z^18 + 106*z^22 + 624*z^26 - 2560*z^30 - 2464*z^34 + 20640*z^38 + 11112*z^42 - 70304*z^46 - 75840*z^50 + 94976*z^54 + 206528*z^58 - 25216*z^62 - 60672*z^66 - 70656*z^70 - 168960*z^74 + 24576*z^78 + 81920*z^82 + 32768*z^86))/
(1 - 6*z^4 - 64*z^8 + 200*z^12 + 1000*z^16 - 3016*z^20 - 3488*z^24 + 24256*z^28 - 23776*z^32 - 104168*z^36 + 203408*z^40 + 184704*z^44 - 443392*z^48 - 14336*z^52 + 151296*z^56 - 145920*z^60 + 263424*z^64 - 317440*z^68 - 36864*z^72 + 966656*z^76 - 573440*z^80 - 131072*z^84).

More terms from Alois P. Heinz, Nov 26 2010

A169767 Number of closed knight's tour diagrams of a 3 X n chessboard that have "Eulerian symmetry".

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 124, 0, 0, 0, 1404, 0, 0, 0, 12824, 0, 0, 0, 126696, 0, 0, 0, 1222368, 0, 0, 0, 11930192, 0, 0, 0, 115974192, 0, 0, 0, 1128943296, 0, 0, 0, 10984783168, 0, 0, 0, 106897187552, 0, 0, 0, 1040241749856

Offset: 4

N. J. A. Sloane, May 10 2010, based on a communication from Don Knuth, Apr 28 2010

nonn

When the board is rotated 180 degrees, the diagram remains the same, and the second half of the tour is the same as the first half before rotation. (If the knight starts at one corner, he reaches the opposite corner after 3n/2 moves.)

D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.

Seiichi Manyama, Table of n, a(n) for n = 4..4057
George Jelliss, Open knight's tours of three-rank boards, Knight's Tour Notes, note 3a (21 October 2000).
George Jelliss, Closed knight's tours of three-rank boards, Knight's Tour Notes, note 3b (21 October 2000).

Cf. A070030, A169696, A169764-A169777.

A169767[n]=0 unless n mod 4 = 2.
Generating function: (2*(8*z^14 + 14*z^18 - 182*z^22 - 168*z^26 + 348*z^30 - 1000*z^34 + 13224*z^38 + 22904*z^42 - 105776*z^46 - 111616*z^50 + 292800*z^54 + 217536*z^58 - 294656*z^62 - 114432*z^66 - 22528*z^70 - 44032*z^74 + 180224*z^78 - 65536*z^82 + 32768*z^86))/
(1 - 6*z^4 - 64*z^8 + 200*z^12 + 1000*z^16 - 3016*z^20 - 3488*z^24 + 24256*z^28 - 23776*z^32 - 104168*z^36 + 203408*z^40 + 184704*z^44 - 443392*z^48 - 14336*z^52 + 151296*z^56 - 145920*z^60 + 263424*z^64 - 317440*z^68 - 36864*z^72 + 966656*z^76 - 573440*z^80 - 131072*z^84).

A169766 Number of closed knight's tour diagrams of a 3 X n chessboard that have "Bergholtian symmetry".

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 8, 0, 48, 0, 152, 0, 352, 0, 1200, 0, 3752, 0, 12912, 0, 34768, 0, 122120, 0, 346128, 0, 1202240, 0, 3337424, 0, 11650864, 0, 32634960, 0, 113539392, 0, 316870592, 0, 1104442752, 0, 3086894528, 0, 10748713792, 0, 30023935744, 0

Offset: 4

N. J. A. Sloane, May 10 2010, based on a communication from Don Knuth, Apr 28 2010

nonn

When the board is rotated 180 degrees, the diagram remains the same, but the tour reverses direction.

D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.

Seiichi Manyama, Table of n, a(n) for n = 4..4057
George Jelliss, Open knight's tours of three-rank boards, Knight's Tour Notes, note 3a (21 October 2000).
George Jelliss, Closed knight's tours of three-rank boards, Knight's Tour Notes, note 3b (21 October 2000).

Cf. A070030, A169696, A169764-A169777.

a(n) = 0 unless n mod 2 = 0.
Generating function: (2*(2*z^10 - 8*z^14 + 24*z^16 - 76*z^18 + 32*z^20 + 288*z^22 - 716*z^24 + 792*z^26 - 336*z^28 - 2908*z^30 + 7896*z^32 - 1464*z^34 - 3432*z^36 + 7416*z^38 - 32616*z^40 - 11792*z^42 + 39888*z^44 + 35472*z^46 + 47968*z^48 + 35776*z^50 - 143424*z^52 - 197824*z^54 - 15552*z^56 - 11008*z^58 + 181376*z^60 + 269440*z^62 + 78080*z^64 + 53760*z^66 + 44288*z^68 - 48128*z^70 - 112640*z^72 - 124928*z^74 - 227328*z^76 - 155648*z^78 + 98304*z^80 + 147456*z^82 + 32768*z^84))/
(1 - 6*z^4 - 64*z^8 + 200*z^12 + 1000*z^16 - 3016*z^20 - 3488*z^24 + 24256*z^28 - 23776*z^32 - 104168*z^36 + 203408*z^40 + 184704*z^44 - 443392*z^48 - 14336*z^52 + 151296*z^56 - 145920*z^60 + 263424*z^64 - 317440*z^68 - 36864*z^72 + 966656*z^76 - 573440*z^80 - 131072*z^84)

More terms extracted from the g.f. by R. J. Mathar, Oct 09 2010

A169768 Number of geometrically distinct closed knight's tours of a 3 X n chessboard that have twofold symmetry.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 24, 0, 24, 0, 276, 0, 176, 0, 2604, 0, 1876, 0, 25736, 0, 17384, 0, 248816, 0, 173064, 0, 2424608, 0, 1668712, 0, 23581056, 0, 16317480, 0, 229513584, 0, 158435296, 0, 2233386048, 0, 1543447264, 0, 21733496960

Offset: 4

N. J. A. Sloane, May 10 2010, based on a communication from Don Knuth, Apr 28 2010

nonn

D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.

Seiichi Manyama, Table of n, a(n) for n = 4..4057
George Jelliss, Open knight's tours of three-rank boards, Knight's Tour Notes, note 3a (21 October 2000).
George Jelliss, Closed knight's tours of three-rank boards, Knight's Tour Notes, note 3b (21 October 2000).

Cf. A070030, A169696, A169764-A169777.

a(n) = (A169765(n)+A169766(n)+A169767(n))/2.
a(n) = 0 unless n mod 2 = 0.
Generating function: (4*z^10 + 24*z^16 - 124*z^18 + 32*z^20 + 212*z^22 - 716*z^24 + 1248*z^26 - 336*z^28 - 5120*z^30 + 7896*z^32 - 4928*z^34 - 3432*z^36 + 41280*z^38 - 32616*z^40 + 22224*z^42 + 39888*z^44 - 140608*z^46 + 47968*z^48 - 151680*z^50 - 143424*z^52 + 189952*z^54 - 15552*z^56 + 413056*z^58 + 181376*z^60 - 50432*z^62 + 78080*z^64 - 121344*z^66 + 44288*z^68 - 141312*z^70 - 112640*z^72 - 337920*z^74 - 227328*z^76 + 49152*z^78 + 98304*z^80 + 163840*z^82 + 32768*z^84 + 65536*z^86)/
(1 - 6*z^4 - 64*z^8 + 200*z^12 + 1000*z^16 - 3016*z^20 - 3488*z^24 + 24256*z^28 - 23776*z^32 - 104168*z^36 + 203408*z^40 + 184704*z^44 - 443392*z^48 - 14336*z^52 + 151296*z^56 - 145920*z^60 + 263424*z^64 - 317440*z^68 - 36864*z^72 + 966656*z^76 - 573440*z^80 - 131072*z^84).

A169771 Number of open knight's tour diagrams of a 3 X n chessboard that have "type F": the endpoints occur in different columns and agree in color with the cells in the nearest corner.

Original entry on oeis.org

2, 0, 0, 52, 224, 520, 1616, 10320, 37024, 125120, 441200, 1798576, 6327472, 22985504, 81178008, 301420176, 1057619944, 3818476576, 13412523392, 48285742208, 168992600680, 602349395456, 2106360581920, 7471875943776, 26073917403304, 92017860990176, 320713651212384

Offset: 4

N. J. A. Sloane, May 10 2010, based on a communication from Don Knuth, Apr 28 2010

nonn

D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.

Seiichi Manyama, Table of n, a(n) for n = 4..1000
George Jelliss, Open knight's tours of three-rank boards, Knight's Tour Notes, note 3a (21 October 2000).
George Jelliss, Closed knight's tours of three-rank boards, Knight's Tour Notes, note 3b (21 October 2000).
D. E. Knuth Generating functions for A169770-A169777 and A169696.

Cf. A070030, A169696, A169764-A169777.

Asymptotic value: 0.02789*3.45059^n.

A169772 Number of open knight's tour diagrams of a 3 X n chessboard that have "type B": the endpoints occur in different columns and disagree in color with the cells in the nearest corner.

Original entry on oeis.org

2, 0, 0, 0, 92, 0, 1064, 0, 14928, 0, 156416, 0, 1785600, 0, 19416704, 0, 211014544, 0, 2261999424, 0, 24067157192, 0, 254242274472, 0, 2669251156032, 0, 27880294589248

Offset: 4

N. J. A. Sloane, May 10 2010, based on a communication from Don Knuth, Apr 28 2010

nonn

D. E. Knuth, Long and skinny knight's tours, in Selected Papers on Fun and Games, to appear, 2010.

Seiichi Manyama, Table of n, a(n) for n = 4..1000
George Jelliss, Open knight's tours of three-rank boards, Knight's Tour Notes, note 3a (21 October 2000).
George Jelliss, Closed knight's tours of three-rank boards, Knight's Tour Notes, note 3b (21 October 2000).
D. E. Knuth Generating functions for A169770-A169777 and A169696.

Cf. A070030, A169696, A169764-A169777.

A169772(n)=0 unless n mod 2 = 0.

Asymptotic value: 0.00144*n*3.11949^n when n is even.

cp's OEIS Frontend

A169696 Number of undirected Knight's tours on a 3 X n board.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A070030 Number of closed Knight's tours on a 3 X 2n board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A169777 Number of geometrically distinct open knight's tours of a 3 X n chessboard.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

A169770 Number of open knight's tour diagrams of a 3 X n chessboard that have "type X": both endpoints occur in the same column.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A169765 Number of closed knight's tour diagrams of a 3 X n chessboard that are symmetric with respect to left-right reflection about a vertical axis.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

Extensions

A169767 Number of closed knight's tour diagrams of a 3 X n chessboard that have "Eulerian symmetry".

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A169766 Number of closed knight's tour diagrams of a 3 X n chessboard that have "Bergholtian symmetry".

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A169768 Number of geometrically distinct closed knight's tours of a 3 X n chessboard that have twofold symmetry.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A169771 Number of open knight's tour diagrams of a 3 X n chessboard that have "type F": the endpoints occur in different columns and agree in color with the cells in the nearest corner.

Views