A383660 -id:A383660 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

1, 0, 1, 30, 0, 148, 8, 78, 9309, 612, 62749, 44202, 42049, 2916485, 147192, 18284136, 13311268, 13008389, 973107552, 51147756, 6190192748, 4557702762, 4311375354, 316985255470, 16552301184, 2015267424300, 1495135512514, 1417634375316, 104324890543686, 5459334927260, 663068761241948

Offset: 9

Don Knuth, May 04 2025

nonn

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

			For n=9 the a(9)=1 example is
  1 14  5 10
  4  9  2 15
 13 18 11  6
  8  3 16
 17 12  7    .

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 = 9..150
Don Knuth, CWEB program with input parameter board,60,5,0,0,5,0,0.gb [the graph "board(50, 6, 0, 0, 5, 0, 0)" generated by the Stanford GraphBase].

Cf. A175855, A383660, A383662, A383663, A383664.

a(5n) = A175855(n).

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

Original entry on oeis.org

6, 0, 2, 302, 8, 151, 19072, 9862, 18202, 1603948, 1067638, 1310791, 107096187, 55488142, 66608924, 6149236417, 3374967940, 4259963914, 402706752421, 239187240144, 292999006211, 26470682075988, 15360134570696, 18595568012716, 1685811256230132, 964730606632516, 1173328484648288

Offset: 11

Don Knuth, May 04 2025

nonn

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

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

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,50,6,0,0,5,0,0.gb [the graph "board(50, 6, 0, 0, 5, 0, 0)" generated by the Stanford GraphBase].

Cf. A175881, A383660, A383661, A383663, A383664.

a(3n) = A175881(n).

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

Original entry on oeis.org

2, 11, 58, 0, 21, 1020, 9309, 1481, 34162, 1295034, 1067638, 2213327, 50139185, 682189688, 144994543, 2607067351, 53099426601, 34524432316, 57716933870, 1388556345255, 16330667126220, 3697750041989, 70341043737487, 1662805965511580, 1250063279938854, 2122662114673944

Offset: 11

Don Knuth, May 04 2025

nonn

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

			For n=11, the first of a(11)=2 solutions is
  1  4 21  6
 20  7  2
  3 22  5
  8 19 10
 11 16 13
 14  9 18
 17 12 15
and the other is obtained by reflecting the bottom four rows:
  1  4 21  6
 20  7  2
  3 22  5
 10 19  8
 13 16 11
 18  9 14
 15 12 17 .

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..147
Don Knuth, CWEB program with input parameter board,42,7,0,0,5,0,0.gb [the graph "board(50, 6, 0, 0, 5, 0, 0)" generated by the Stanford GraphBase].

Cf. A193054, A383660, A383661, A383662, A383664.

a(7n) = A193054(n).

A383664 Number of closed knight's tours in the first 2n cells of an 8 X ceiling(2n/8) board.

Original entry on oeis.org

4, 12, 212, 0, 50, 4525, 101730, 44202, 66034, 2408624, 69362264, 55488142, 101343548, 2398536889, 43391615822, 34524432316, 52661182514, 1231713564493, 20780788492646, 13267364410532, 21515340977481, 552407941427835, 10211663162678661, 7112881119092574, 11873618786859165

Offset: 13

Don Knuth, May 04 2025

nonn

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

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

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 = 13..96
Don Knuth, CWEB program with input parameter board,32,8,0,0,5,0,0.gb [the graph "board(50, 6, 0, 0, 5, 0, 0)" generated by the Stanford GraphBase].

Cf. A193055, A383660, A383661, A383662, A383663.

a(4n) = A193055(n).

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A383664 Number of closed knight's tours in the first 2n cells of an 8 X ceiling(2n/8) board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula