A269565 -id:A269565 - cp's OEIS frontend

A096970 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 the same row or column.

1, 8, 1512, 22394880, 50657369241600, 28606505102329400524800, 5959275438217048853558620520448000

Offset: 1

John W. Layman, Jul 16 2004

Suggested by Leroy Quet, Jul 05 2004.

For n >= 2, number of (directed) Hamiltonian paths on the n X n rook graph. - Eric W. Weisstein, Dec 16 2013

			Among the 4 X 4 grids counted is:
1   2  3 10
15  6  5 11
14 13  4 12
16  7  8  9

Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Rook Graph
Index entries for sequences related to graphs, Hamiltonian

Cf. A096969, A269561, A269565.

a(5) from Eric W. Weisstein, Dec 28 2013

a(6)-a(7) from Andrew Howroyd, Feb 29 2016

A269562 Array read by antidiagonals: T(n,m) is the number of Hamiltonian cycles in the rook graph K_n X K_m.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 3, 3, 3, 3, 12, 30, 48, 30, 12, 60, 480, 1566, 1566, 480, 60, 360, 12000, 126120, 284112, 126120, 12000, 360, 2520, 430920, 18153720, 122330880, 122330880, 18153720, 430920, 2520, 20160, 21052080, 4357332000, 112777827840, 335750676480, 112777827840, 4357332000, 21052080, 20160

Offset: 1

Andrew Howroyd, Feb 29 2016

Equivalently, the number of rook tours on an n X m lattice.

2*T(n,m) is divisible by (n-1)!*(m-1)!. - Andrew Howroyd, Feb 08 2021

			Array begins:
=============================================================
n\m |   1      2          3            4                5
----+--------------------------------------------------------
  1 |   0      0          1            3               12 ...
  2 |   0      1          3           30              480 ...
  3 |   1      3         48         1566           126120 ...
  4 |   3     30       1566       284112        122330880 ...
  5 |  12    480     126120    122330880     335750676480 ...
  6 |  60  12000   18153720 112777827840 2190773906150400 ...
  7 | 360 430920 4357332000 ...
     ...

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

Column 1 is A001710(n-1) for n >= 3.
Columns 2..4 are A276356, A341498, A341499.
Main diagonal is A269561.
Cf. A269565, A286418.

From Andrew Howroyd, Feb 08 2021: (Start)
T(n,m) = T(m,n).
T(n,1) = (n-1)!/2 for n >= 3. (End)

A286418 Array read by antidiagonals: T(n,m) is the number of (undirected) cycles in the rook graph K_n X K_m.

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 7, 14, 14, 7, 37, 170, 312, 170, 37, 197, 2904, 13945, 13945, 2904, 197, 1172, 74779, 1241696, 3228524, 1241696, 74779, 1172, 8018, 2751790, 196846257, 1723178763, 1723178763, 196846257, 2751790, 8018

Offset: 1

Andrew Howroyd, May 08 2017

			Table starts:
================================================
m\n  1    2       3          4             5
--+---------------------------------------------
1 |  0    0       1          7            37 ...
2 |  0    1      14        170          2904 ...
3 |  1   14     312      13945       1241696 ...
4 |  7  170   13945    3228524    1723178763 ...
5 | 37 2904 1241696 1723178763 6198979538330 ...
  ...

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

Main diagonal is A234624.
Columns 1..3 are A002807, A341500, A341501.
Cf. A269562, A269565.

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

A329319 Number of (directed) Hamiltonian paths in K_{n} X K_{3}.

Original entry on oeis.org

6, 60, 1512, 83520, 8869680, 1621680480, 472907393280, 207307564531200, 130417226086775040, 113438068529746060800, 132325125941706622848000, 201817805274824171102208000

Offset: 1

Mikhail Kurkov, Nov 10 2019

Equivalently, number of full spectrum rook's walks on a (n X 3) board.

Column 3 of A269565.

Cf. A096121.

A360877 Array read by antidiagonals: T(m,n) is the number of (undirected) paths in the rook graph K_m X K_n.

Original entry on oeis.org

0, 1, 1, 6, 12, 6, 30, 129, 129, 30, 160, 1984, 4536, 1984, 160, 975, 45945, 310542, 310542, 45945, 975, 6846, 1524156, 38298270, 111933456, 38298270, 1524156, 6846

Offset: 1

Andrew Howroyd, Feb 25 2023

			Array begins:
==============================================
m\n|   1     2        3         4        5 ...
---+------------------------------------------
1  |   0     1        6        30      160 ...
2  |   1    12      129      1984    45945 ...
3  |   6   129     4536    310542 38298270 ...
4  |  30  1984   310542 111933456 ...
5  | 160 45945 38298270 ...
  ...

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

Main diagonal is A288967.
Rows 1..2 are A038155, A360878.
Cf. A269562, A269565, A286418, A360851, A360855.

cp's OEIS Frontend

A096970 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 the same row or column.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A269562 Array read by antidiagonals: T(n,m) is the number of Hamiltonian cycles in the rook graph K_n X K_m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A286418 Array read by antidiagonals: T(n,m) is the number of (undirected) cycles in the rook graph K_n X K_m.

Views

Author

Keywords

Examples

Links

Crossrefs

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

A329319 Number of (directed) Hamiltonian paths in K_{n} X K_{3}.

Views

Author

Keywords

Comments

Crossrefs

A360877 Array read by antidiagonals: T(m,n) is the number of (undirected) paths in the rook graph K_m X K_n.

Views

Author

Keywords

Examples

Links

Crossrefs