A286418 -id:A286418 - cp's OEIS frontend

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

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)

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)

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

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

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 4, 2, 2, 4, 10, 8, 6, 8, 10, 20, 20, 16, 16, 20, 20, 35, 40, 35, 32, 35, 40, 35, 56, 70, 66, 60, 60, 66, 70, 56, 84, 112, 112, 104, 100, 104, 112, 112, 84, 120, 168, 176, 168, 160, 160, 168, 176, 168, 120, 165, 240, 261, 256, 245, 240, 245, 256, 261, 240, 165

Offset: 1

Andrew Howroyd, Feb 24 2023

A triangle is a clique of size 3. Also, a 3-cycle.

			Array begins:
=======================================
m\n|  1   2   3   4   5   6   7   8 ...
---+-----------------------------------
1  |  0   0   1   4  10  20  35  56 ...
2  |  0   0   2   8  20  40  70 112 ...
3  |  1   2   6  16  35  66 112 176 ...
4  |  4   8  16  32  60 104 168 256 ...
5  | 10  20  35  60 100 160 245 360 ...
6  | 20  40  66 104 160 240 350 496 ...
7  | 35  70 112 168 245 350 490 672 ...
8  | 56 112 176 256 360 496 672 896 ...
  ...

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

Main diagonal is A288961.
Rows n=1..3 are A000292(n-2), A007290, A060354.
Cf. A286418, A360853.

T(m, n) = m*binomial(n,3) + n*binomial(m,3)

T(m,n) = m*binomial(n,3) + n*binomial(m,3).

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

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

A341500 Number of cycles in the 2 X n rook graph.

Original entry on oeis.org

0, 1, 14, 170, 2904, 74779, 2751790, 137080628, 8882440224, 726325289493, 73173672616318, 8906815805139614, 1288823180820993752, 218690604655001166063, 43009037666992387906942, 9705063652363696926178792, 2490696756572714604529691648, 721374035463654709543727643561

Offset: 1

Andrew Howroyd, Feb 21 2021

nonn

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

Column 2 of A286418.

a(n)={sum(k=3, n, binomial(n,k)*(k-1)!) + sum(k=1, n\2, k*binomial(n,2*k) * binomial(2*k,k) * sum(j=0, n-2*k, binomial(n-2*k,j)*(k+j-1)!)^2)/2}

a(n) = (Sum_{k=3..n} binomial(n,k)*(k-1)!) + (1/2)*Sum_{k=1..floor(n/2)} (k*binomial(n,2*k) * binomial(2*k,k) * (Sum_{j=0..n-2*k} binomial(n-2*k,j)*(k+j-1)!)^2).

A341501 Number of cycles in the 3 X n rook graph.

Original entry on oeis.org

1, 14, 312, 13945, 1241696, 196846257, 50828091505, 20024754905438, 11449549613245851, 9132012077055635872, 9838890888977921645318, 13943876645976749962479951, 25420022651057340998037064594, 58486800791746378910741227427387

Offset: 1

Andrew Howroyd, Feb 21 2021

nonn

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

Column 3 of A286418.

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

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

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

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

Views

Author

Keywords

Links

Crossrefs

Extensions

A360855 Array read by antidiagonals: T(m,n) is the number of triangles in the rook graph K_m X 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

A341500 Number of cycles in the 2 X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A341501 Number of 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