login
A360853
Array read by antidiagonals: T(m,n) is the number of induced cycles in the rook graph K_m X K_n.
5
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,7
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.
LINKS
Eric Weisstein's World of Mathematics, Rook Graph.
FORMULA
T(m,n) = A360849(m,n) + A360855(m,n).
T(m,n) = T(n,m).
EXAMPLE
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 ...
...
PROG
(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)
CROSSREFS
Main diagonal is A360854.
Rows 1..2 are A000292(n-2), A000330(n-1).
Cf. A360196, A360849, A360851 (induced paths), A360855 (triangles).
Sequence in context: A222703 A222587 A222378 * A094848 A308740 A349990
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Feb 24 2023
STATUS
approved