A360855 -id:A360855 - cp's OEIS frontend

A288961 Number of 3-cycles in the n X n rook graph.

0, 0, 6, 32, 100, 240, 490, 896, 1512, 2400, 3630, 5280, 7436, 10192, 13650, 17920, 23120, 29376, 36822, 45600, 55860, 67760, 81466, 97152, 115000, 135200, 157950, 183456, 211932, 243600, 278690, 317440, 360096, 406912, 458150, 514080, 574980, 641136, 712842, 790400

Offset: 1

Eric W. Weisstein, Jun 20 2017

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Rook Graph
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A288962 (4-cycles), A288963 (5-cycles), A288960 (6-cycles).

Main diagonal of A360855.

Table[n^2 (n - 1) (n - 2)/3, {n, 20}]
Table[2 n Binomial[n, 3], {n, 20}]
LinearRecurrence[{5, -10, 10, -5, 1}, {0, 0, 6, 32, 100}, 20]
CoefficientList[Series[-((2 x^2 (3 + x))/(-1 + x)^5), {x, 0, 20}], x]

a(n) = {2*n*binomial(n,3)} \\ Andrew Howroyd, Apr 26 2020

a(n) = 2*n*binomial(n,3).
a(n) = 5*a(n-1)-10*a(n-2)+10*a(n-3)-5*a(n-4)+a(n-5).
G.f.: (-2*x^3*(3+x))/(-1+x)^5.

Terms a(31) and beyond from Andrew Howroyd, Apr 26 2020

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

Original entry on oeis.org

0, 0, 0, 1, 1, 1, 4, 5, 5, 4, 10, 14, 21, 14, 10, 20, 30, 58, 58, 30, 20, 35, 55, 125, 236, 125, 55, 35, 56, 91, 231, 720, 720, 231, 91, 56, 84, 140, 385, 1754, 4040, 1754, 385, 140, 84, 120, 204, 596, 3654, 15550, 15550, 3654, 596, 204, 120

Offset: 1

Andrew Howroyd, Feb 24 2023

Induced cycles are sometimes called chordless cycles (but some definitions require chordless cycles to have a cycle length of at least 4). See A360849 for the version that excludes triangles.

			Array begins:
==========================================================
m\n|  1   2   3    4      5       6        7         8 ...
---+------------------------------------------------------
1  |  0   0   1    4     10      20       35        56 ...
2  |  0   1   5   14     30      55       91       140 ...
3  |  1   5  21   58    125     231      385       596 ...
4  |  4  14  58  236    720    1754     3654      6808 ...
5  | 10  30 125  720   4040   15550    45395    109840 ...
6  | 20  55 231 1754  15550  114105   526505   1776676 ...
7  | 35  91 385 3654  45395  526505  4662721  24865260 ...
8  | 56 140 596 6808 109840 1776676 24865260 256485936 ...
  ...

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

Main diagonal is A360854.
Rows 1..2 are A000292(n-2), A000330(n-1).
Cf. A360196, A360849, A360851 (induced paths), A360855 (triangles).

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

T(m,n) = A360849(m,n) + A360855(m,n).

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

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.

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

Original entry on oeis.org

0, 1, 1, 3, 4, 3, 6, 9, 9, 6, 10, 16, 18, 16, 10, 15, 25, 30, 30, 25, 15, 21, 36, 45, 48, 45, 36, 21, 28, 49, 63, 70, 70, 63, 49, 28, 36, 64, 84, 96, 100, 96, 84, 64, 36, 45, 81, 108, 126, 135, 135, 126, 108, 81, 45, 55, 100, 135, 160, 175, 180, 175, 160, 135, 100, 55

Offset: 1

Andrew Howroyd, May 20 2025

			Array begins:
=======================================
n\m |  1  2   3   4   5   6   7   8 ...
----+----------------------------------
  1 |  0  1   3   6  10  15  21  28 ...
  2 |  1  4   9  16  25  36  49  64 ...
  3 |  3  9  18  30  45  63  84 108 ...
  4 |  6 16  30  48  70  96 126 160 ...
  5 | 10 25  45  70 100 135 175 220 ...
  6 | 15 36  63  96 135 180 231 288 ...
  7 | 21 49  84 126 175 231 294 364 ...
  8 | 28 64 108 160 220 288 364 448 ...
  ...

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

Main diagonal is A045991.
Columns 1..6 are A000217(n-1), A000290, A045943, A054000, A269457(n-1), A067707.
Cf. A003991 (number of vertices), A360855 (triangles), A384120 (all cliques).

Table[#*Binomial[m, 2] + m*Binomial[#, 2] &[n - m + 1], {n, 11}, {m, n}] // Flatten (* Michael De Vlieger, May 22 2025 *)

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

T(n,m) = n*binomial(m,2) + m*binomial(n,2).
T(n,m) = binomial(n*m,2) - 2*binomial(n,2)*binomial(m,2).
T(n,m) = T(m,n).

cp's OEIS Frontend

A288961 Number of 3-cycles in the n X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula