A096970 -id:A096970 - cp's OEIS frontend

A269565 Array read by antidiagonals: T(n,m) is the number of (directed) Hamiltonian paths in K_n X K_m.

1, 2, 2, 6, 8, 6, 24, 60, 60, 24, 120, 816, 1512, 816, 120, 720, 17520, 83520, 83520, 17520, 720, 5040, 550080, 8869680, 22394880, 8869680, 550080, 5040, 40320, 23839200, 1621680480, 13346910720, 13346910720, 1621680480, 23839200, 40320

Offset: 1

Andrew Howroyd, Feb 29 2016

Equivalently, the number of directed Hamiltonian paths on the n X m rook graph.
Conjecture: T(n,m) mod n!*m! = 0. - Mikhail Kurkov, Feb 08 2019
The above conjecture is true since a path defines an ordering on the rows and columns by the order in which they are first visited by the path. Every permutation of rows and columns therefore gives a different path. - Andrew Howroyd, Feb 08 2021

			Array begins:
===========================================================
n\m|    1      2        3            4               5
---+-------------------------------------------------------
1  |    1,     2,       6,          24,            120, ...
2  |    2,     8,      60,         816,          17520, ...
3  |    6,    60,    1512,       83520,        8869680, ...
4  |   24,   816,   83520,    22394880,    13346910720, ...
5  |  120, 17520, 8869680, 13346910720, 50657369241600, ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..96
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal is A096970.
Columns 2..3 are A096121, A329319.
Cf. A286418, A269562.

From Andrew Howroyd, Oct 20 2019: (Start)
T(n,m) = T(m,n).
T(n,1) = n!. (End)

A096969 Number of ways to number the cells of an n X n square grid with 1,2,3,...,n^2 so that successive integers are in adjacent cells (horizontally or vertically).

Original entry on oeis.org

1, 8, 40, 552, 8648, 458696, 27070560, 6046626568, 1490832682992, 1460089659025264, 1573342970540617696, 6905329711608694708440, 33304011435341069362631160, 663618176813467308855850585056, 14527222735920532980525200234503048

Offset: 1

John W. Layman, Jul 16 2004, at the suggestion of Leroy Quet, Jul 05 2004

Number of directed Hamiltonian paths in (n X n)-grid graph. - Max Alekseyev, May 03 2009

			One of the 8648 numberings of a 5 X 5 grid is
.
  3---2---1  20--21
  |           |   |
  4  17--18--19  22
  |   |           |
  5  16--15--14  23
  |           |   |
  6   9--10  13  24
  |   |   |   |   |
  7---8  11--12  25

Andrew Howroyd, Table of n, a(n) for n = 1..17
Nicolas Bělohoubek, All possible paths in 4th term (552) presented by A..D 1..4 coordination system.
Nicolas Bělohoubek, All possible paths in 5th term (8648) presented by A..E 1..5 coordination system.
Nicolas Bělohoubek, All possible paths in 5th term (8648) in image, blue to red.
Stéphane Duguay and Steven Pigeon, Comparison of Pixel Correlation Induced by Space-Filling Curves on 2D Image Data, The 10th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications (Metz, France, 2019) Vol. 1, 294-297.
Mary Grace Hanson and David A. Nash, Minimal and maximal Numbrix puzzles, arXiv:1706.09389 [math.CO], 2017.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Hamiltonian Path
Index entries for sequences related to graphs, Hamiltonian

Cf. A120443, A096970, A143246, A137891, A158651.

Conjecture: Limit_{n->oo} log_(n+1)!(a(n+1)) - log_n!(a(n)) = c, where 0.09 < c < 0.11. - Nicolas Bělohoubek, Jun 12 2022

a(7) from Giovanni Resta, May 12 2006

a(8)-a(15) added by Andrew Howroyd, Dec 20 2015

A234624 Number of (undirected) cycles in the n X n rook graph.

Original entry on oeis.org

0, 1, 312, 3228524, 6198979538330, 3366323909717796339009

Offset: 1

Eric W. Weisstein, Dec 28 2013

Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal of A286418.

Cf. A269561, A096970.

a(6) from Andrew Howroyd, May 08 2017

A269561 Number of (undirected) Hamiltonian cycles in the n X n rook graph K_n X K_n.

Original entry on oeis.org

1, 48, 284112, 335750676480, 112249362914249932800, 14994936423694913432308324761600

Offset: 2

Andrew Howroyd, Feb 29 2016

Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Rook Graph

Cf. A269562, A096970, A003763, A222199.

Name adjusted by Eric W. Weisstein, May 06 2019

A096121 Number of full spectrum rook's walks on a (2 X n) board.

Original entry on oeis.org

2, 8, 60, 816, 17520, 550080, 23839200, 1365799680, 100053999360, 9127781913600, 1015061950425600, 135193044668774400, 21248464632595200000, 3891825697262043340800, 821745573997874093568000, 198152975926832672858112000, 54121124248225908770856960000, 16621698830590738881776812032000

Offset: 1

Hugo van der Sanden, Jul 22 2004

A rook must land on each square exactly once, but may start and end anywhere and may intersect its own path.

This also gives the number of ways to arrange n pairs of shoes in a row so that no left shoe is next to a right shoe from a different pair. - Jerrold Grossman, Jul 19 2024

			Tagging the squares on a (3 X 2) board with A,B,C/D,E,F, the 10 tours starting at A are ABCFDE, ABCFED, ABEDFC, ACBEDF, ACBEFD, ACFDEB, ADEBCF, ADEFCB, ADFCBE, ADFEBC. There are a similar 10 tours starting at each of the other 5 squares, so a(3) = 6 * 10 = 60.

Inspired by Leroy Quet in a Jul 05 2004 posting to the Seqfan mailing list.

Y. Cha, Closed form solutions of difference equations (2011) PhD Thesis, Florida State University, Example 5.1.1

Column 2 of A269565.

Cf. A096970 and references to "rook tours" or "rook walks".

a[1]=2; a[2]=8; a[n_]:= n*(n-1)*(a[n-1] + a[n-2]); Array[a,18] (* Stefano Spezia, Jul 19 2024 *)

D-finite with recurrence: a(n+1) = n*(n+1)*(a(n) + a(n-1)) for n > 1.
Further refinement gives: a(n+1) = 2*(n+1)! * Sum_{k=0..floor(n/2)} (P(n-k, k) * C(n-k, k) + P(n-k, k+1) * C(n-1-k, i)), where P(i,j) = i!/j!.
Conjecture: a(n) = 2*n!*A102038(n). - Mikhail Kurkov, Feb 07 2019

a(16)-a(18) from Stefano Spezia, Jul 19 2024

A234632 Numbers of directed Hamiltonian paths in the n X n black bishop graph.

Original entry on oeis.org

2, 8, 192, 50752, 64264704, 2591115982336, 458135084510273536, 5255224440224669298917376

Offset: 2

Eric W. Weisstein, Dec 28 2013

Eric Weisstein's World of Mathematics, Bishop Graph
Eric Weisstein's World of Mathematics, Black Bishop Graph
Eric Weisstein's World of Mathematics, Hamiltonian Path

Cf. A234637, A096970.

a(3) prepended and a(8)-a(9) from Andrew Howroyd, Feb 21 2016

a(2) prepended by Eric W. Weisstein, Nov 16 2016

A234637 Number of directed Hamiltonian paths in the n X n white bishop graph.

Original entry on oeis.org

2, 8, 192, 24512, 64264704, 784014157824, 458135084510273536, 1135180621552183662673920

Offset: 2

Eric W. Weisstein, Dec 28 2013

Eric Weisstein's World of Mathematics, Bishop Graph
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, White Bishop Graph

Cf. A234632, A096970.

a(3) prepended and a(8)-a(9) from Andrew Howroyd, Feb 21 2016

a(2) prepended by Eric W. Weisstein, Nov 16 2016

A288967 Number of (undirected) paths on the n X n rook graph.

Original entry on oeis.org

0, 12, 4536, 111933456

Offset: 1

Eric W. Weisstein, Jun 20 2017

Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal of A360877.

Cf. A096970, A234624.

A308141 Number of (undirected) Hamiltonian paths in the n X n rook graph.

Original entry on oeis.org

0, 4, 756, 11197440, 25328684620800, 14303252551164700262400, 2979637719108524426779310260224000

Offset: 1

Eric W. Weisstein, May 14 2019

Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Rook Graph

Cf. A096970.

a(n) = A096970(n)/2.

cp's OEIS Frontend

A269565 Array read by antidiagonals: T(n,m) is the number of (directed) Hamiltonian paths in K_n X K_m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A096969 Number of ways to number the cells of an n X n square grid with 1,2,3,...,n^2 so that successive integers are in adjacent cells (horizontally or vertically).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A234624 Number of (undirected) cycles in the n X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A269561 Number of (undirected) Hamiltonian cycles in the n X n rook graph K_n X K_n.

Views

Author

Keywords

Links

Crossrefs

Extensions

A096121 Number of full spectrum rook's walks on a (2 X n) board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A234632 Numbers of directed Hamiltonian paths in the n X n black bishop graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A234637 Number of directed Hamiltonian paths in the n X n white bishop graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A288967 Number of (undirected) paths on the n X n rook graph.

Views

Author

Keywords

Links

Crossrefs

A308141 Number of (undirected) Hamiltonian paths in the n X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Formula