A175855 -id:A175855 - cp's OEIS frontend

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

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

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

cp's OEIS Frontend

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