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

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

Author

Andrew Howroyd, Feb 24 2023

Keywords

• nonn
• tabl

Comments

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.

Examples

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

Links

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

Crossrefs

Main diagonal is A360854.

Rows 1..2 are A000292(n-2), A000330(n-1).

Cf. A360196, A360849, A360851 (induced paths), A360855 (triangles).

Programs

PARI

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)

Formula

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

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