A269562 -id:A269562 - cp's OEIS frontend

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

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.

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

Original entry on oeis.org

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)

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

A276356 Number of Hamiltonian cycles in the Cartesian product graph K_2 times K_n.

Original entry on oeis.org

0, 1, 3, 30, 480, 12000, 430920, 21052080, 1343381760, 108519626880, 10825535952000, 1307042125804800, 187849403155814400, 31691651643235584000, 6201948133744691328000, 1393497414722424211200000, 356287752381703180566528000, 102850159977463464656842752000

Offset: 1

Joel B. Lewis, Aug 31 2016

Twice the index k in the summation formula is the number of copies of K_2 in the cycle; this accounts for the factor binomial(n,2k). The remaining factors in each summand count the ways to connect these points to the others within each copy of K_n so that the result is a single cycle.

			For n = 1, the graph is K_2 and has no Hamiltonian cycles.
For n = 2, the graph is C_4, with a single Hamiltonian cycle.
For n = 3, the graph is the complement of C_6; each Hamiltonian cycle is determined by the choice of two edges of the 3 copies of K_2 to include.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Eric Weisstein's World of Mathematics, Rook Graph.
Notamathematician et al., On a A089039 and pair of sequences with simple recursion, MathOverflow, 2024.

Second column of A269562.

Cf. A001040, A001053, A089039 (directed cycles).

a(n) = sum(k=1, n\2, binomial(n, 2*k) * (2*k-1)! * ((n-k-1)!/(k-1)!)^2); \\ Michel Marcus, Aug 31 2016

a(n) = Sum_{k=1..floor(n/2)} binomial(n, 2k) * (2k - 1)! * ((n - k - 1)! / (k - 1)!)^2.
For n > 1, a(n) = A089039(n)/2. - Mikhail Kurkov, Feb 10 2019
For n > 1, a(n) = ((n-1)!/2)*(A001040(n-1) + A001053(n)). - Conjectured by Mikhail Kurkov, Feb 10 2019; proved (see MO link) by Max Alekseyev, Apr 23 2024

A360849 Array read by antidiagonals: T(m,n) is the number of (undirected) cycles in the complete bipartite graph K_{m,n}.

Original entry on oeis.org

0, 0, 0, 0, 1, 0, 0, 3, 3, 0, 0, 6, 15, 6, 0, 0, 10, 42, 42, 10, 0, 0, 15, 90, 204, 90, 15, 0, 0, 21, 165, 660, 660, 165, 21, 0, 0, 28, 273, 1650, 3940, 1650, 273, 28, 0, 0, 36, 420, 3486, 15390, 15390, 3486, 420, 36, 0, 0, 45, 612, 6552, 45150, 113865, 45150, 6552, 612, 45, 0

Offset: 1

Andrew Howroyd, Feb 23 2023

Also, T(m,n) is the number of chordless cycles of length >= 4 in the m X n rook graph.

			Array begins:
========================================================
m\n| 1  2   3    4      5       6        7         8 ...
---+----------------------------------------------------
1  | 0  0   0    0      0       0        0         0 ...
2  | 0  1   3    6     10      15       21        28 ...
3  | 0  3  15   42     90     165      273       420 ...
4  | 0  6  42  204    660    1650     3486      6552 ...
5  | 0 10  90  660   3940   15390    45150    109480 ...
6  | 0 15 165 1650  15390  113865   526155   1776180 ...
7  | 0 21 273 3486  45150  526155  4662231  24864588 ...
8  | 0 28 420 6552 109480 1776180 24864588 256485040 ...
  ...
Lower half of array as triangle T(n,k) for 1 <= k <= n begins:
  0;
  0,  1;
  0,  3,  15;
  0,  6,  42,  204;
  0, 10,  90,  660,  3940;
  0, 15, 165, 1650, 15390, 113865;
  0, 21, 273, 3486, 45150, 526155, 4662231;
  ...

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

Rows 1..3 are A000004, A000217(n-1), A059270(n-1).
Main diagonal is A070968.
Cf. A269562, A286418, A360850 (paths), A360853.

T(m,n) = sum(j=2, min(m,n), binomial(m,j)*binomial(n,j)*j!*(j-1)!/2)

T(m,n) = Sum_{j=2..min(m,n)} binomial(m,j)*binomial(n,j)*j!*(j-1)!/2.

T(m,n) = T(n,m).

A341498 Number of Hamiltonian cycles in the 3 X n rook graph.

Original entry on oeis.org

1, 3, 48, 1566, 126120, 18153720, 4357332000, 1619499374640, 883124275824000, 677267024315091840, 706022078404964428800, 972890835488032591468800, 1731258722423272253052441600, 3900512495412914495014418918400, 10938873545450798558110852249497600

Offset: 1

Andrew Howroyd, Feb 21 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..30

Column 3 of A269562.

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.

A341499 Number of Hamiltonian cycles in the 4 X n rook graph.

Original entry on oeis.org

3, 30, 1566, 284112, 122330880, 112777827840, 196166156901120, 593448176589649920, 2927894041560795955200, 22384255485528968471838720, 254368264421726727280223846400, 4150617533254451866274537825894400, 94460232869419006706028435289512345600

Offset: 1

Andrew Howroyd, Feb 21 2021

nonn

Column 4 of A269562.

cp's OEIS Frontend

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

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

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

Views

Author

Keywords

Links

Crossrefs

Extensions

A276356 Number of Hamiltonian cycles in the Cartesian product graph K_2 times K_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A360849 Array read by antidiagonals: T(m,n) is the number of (undirected) cycles in the complete bipartite graph K_{m,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A341498 Number of Hamiltonian cycles in the 3 X n rook graph.

Views

Author

Keywords

Links

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

A341499 Number of Hamiltonian cycles in the 4 X n rook graph.

Views

Author

Keywords

Crossrefs