A070030 -id:A070030 - cp's OEIS frontend

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

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

Offset: 1

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

a(2n) = A070030(n), a(2n+1) = 0.

A070030 is the main entry for this sequence. See that entry for much more information.

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..2031 (terms 1..1000 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, A169765-A169777.

CoefficientList[Series[(16*z^10 +80*z^12 -544*z^14 -1856*z^16 +8080*z^18 +9856*z^20 -50864*z^22 -64*z^24 +152576*z^26 -130816*z^28 -214272*z^30 +245760*z^32 +222208*z^34 +44544*z^36 -53248*z^38 -352256*z^40 +81920*z^42 +32768*z^44) / (1 -6*z^2 -64*z^4 +200*z^6 +1000*z^8 -3016*z^10 -3488*z^12 +24256*z^14 -23776*z^16 -104168*z^18 +203408*z^20 +184704*z^22 -443392*z^24 -14336*z^26 +151296*z^28 -145920*z^30 +263424*z^32 -317440*z^34 -36864*z^36 +966656*z^38 -573440*z^40 -131072*z^42), {z,0,50}], z] (* Harvey P. Dale, Feb 12 2013 *)

Asymptotic value .0001899*3.11949^n when n is even.

Generating function: (16*z^10 + 80*z^12 - 544*z^14 - 1856*z^16 + 8080*z^18 + 9856*z^20 - 50864*z^22 - 64*z^24 + 152576*z^26 - 130816*z^28 - 214272*z^30 + 245760*z^32 + 222208*z^34 + 44544*z^36 - 53248*z^38 - 352256*z^40 + 81920*z^42 + 32768*z^44)/(1 - 6*z^2 - 64*z^4 + 200*z^6 + 1000*z^8 - 3016*z^10 - 3488*z^12 + 24256*z^14 - 23776*z^16 - 104168*z^18 + 203408*z^20 + 184704*z^22 - 443392*z^24 - 14336*z^26 + 151296*z^28 - 145920*z^30 + 263424*z^32 - 317440*z^34 - 36864*z^36 + 966656*z^38 - 573440*z^40 - 131072*z^42).

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.

A383660 Number of closed knight's tours in the first 2n cells of a 3 X ceiling(2n/3) board.

Original entry on oeis.org

4, 0, 4, 24, 16, 56, 306, 176, 456, 2632, 1536, 4828, 26788, 15424, 44952, 254288, 147728, 448032, 2502568, 1448416, 4310048, 24228704, 14060048, 42195584, 236335248, 136947616, 409403328, 2297294496, 1332257856, 3989883552, 22366625344, 12965578752, 38798663104, 217604833360, 126169362176

Offset: 11

Don Knuth, May 04 2025

nonn

If n is not a multiple of 3, the rightmost column has only 2n mod 3 rows (see example).

			For n=11 the a(11)=4 solutions are
  1  4  7 10 17 20 15 12
  6  9  2 21 14 11 18
  3 22  5  8 19 16 13    ;
  1  4  7 14 11 20  9 18
  6 15  2 21  8 17 12
  3 22  5 16 13 10 19    ;
  1  4 21 12 15  6 17  8
 20 11  2  5 18  9 14
  3 22 19 10 13 16  7    ;
  1  4 21 18  9  6 11 14
 20 17  2  5 12 15  8
  3 22 19 16  7 10 13    .

Donald E. Knuth, Hamiltonian paths and cycles, Prefascicle 8a of The Art of Computer Programming (work in progress, 2025).

Don Knuth, Table of n, a(n) for n = 11..150
Don Knuth, CWEB program with input parameter board,100,3,0,0,5,0,0.gb [the graph "board(50, 6, 0, 0, 5, 0, 0)" generated by the Stanford GraphBase.

Cf. A070030, A383661, A383662, A383663, A383664.

a(3n) = A070030(n).

A175881 Number of closed Knight's tours on a 6 X n board.

Original entry on oeis.org

0, 0, 0, 0, 8, 9862, 1067638, 55488142, 3374967940, 239187240144, 15360134570696, 964730606632516, 61989683445413228, 4005716717182224826, 255967892553030600920, 16378998506224697063588, 1050504687249683771795632, 67351449674771471216148786, 4314151246752166099728445868

Offset: 1

Johan de Ruiter, Dec 05 2010

nonn

Could you please say how you calculated these numbers? - N. J. A. Sloane, Dec 05 2010?

I kept track of pairs of loose ends within the two rightmost columns of a 6 X n board, assuming that everything to the left of these two columns is fully connected and that there are no cycles (or one if this is a final state). Next I added a new column and connected it to the rightmost two columns in all ways such that there are no cycles formed(or one if this results in a final state) and the leftmost column in the current state is fully connected and can be dropped. From this followed a transition matrix. I can provide a reference to my writeup once it is completed and has been accepted by my supervisor. - Johan de Ruiter, Dec 05 2010

			The smallest 6 X n board admitting a closed Knight's tour is the 6 X 5, on which there are 8 such tours.

Johan de Ruiter, Table of n, a(n) for n = 1..40
J. de Ruiter, Counting Domino Coverings and Chessboard Cycles, 2010.

A070030 deals with 3 X 2n boards, A175855 with 5 X 2n boards.

Cf. A383662.

a(n) = A383662(3n). - Don Knuth, May 05 2025

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

A158074 Number of (directed) Hamiltonian cycles on a 3 X (2n) knight's tour graph.

Original entry on oeis.org

0, 0, 0, 0, 32, 352, 3072, 30848, 295456, 2896832, 28120096, 273895232, 2664515712, 25931157504, 252338724352, 2455552258304, 23895692937216, 232533011307776, 2262837745837568, 22020130538878208, 214282979451801088, 2085233793265765376, 20291876152214982656

Offset: 1

Eric W. Weisstein, Mar 13 2009

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Knight's Tour

Cf. A070030 for details and references.

a(n) = 2*A070030(n).

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. (See A070030) - Seiichi Manyama, Dec 16 2016

Extended by Eric W. Weisstein, Mar 18 2009

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).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

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

A383660 Number of closed knight's tours in the first 2n cells of a 3 X ceiling(2n/3) board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A175881 Number of closed Knight's tours on a 6 X n board.

Views

Author

Keywords

Comments

Examples

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

A158074 Number of (directed) Hamiltonian cycles on a 3 X (2n) knight's tour graph.

Views

Author

Keywords

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