login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #9 Feb 27 2023 22:51:46

%S 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,

%T 125,55,35,56,91,231,720,720,231,91,56,84,140,385,1754,4040,1754,385,

%U 140,84,120,204,596,3654,15550,15550,3654,596,204,120

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

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

%H Andrew Howroyd, <a href="/A360853/b360853.txt">Table of n, a(n) for n = 1..1275</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RookGraph.html">Rook Graph</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Cycle_(graph_theory)">Cycle (graph theory)</a>.

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

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

%e Array begins:

%e ==========================================================

%e m\n| 1 2 3 4 5 6 7 8 ...

%e ---+------------------------------------------------------

%e 1 | 0 0 1 4 10 20 35 56 ...

%e 2 | 0 1 5 14 30 55 91 140 ...

%e 3 | 1 5 21 58 125 231 385 596 ...

%e 4 | 4 14 58 236 720 1754 3654 6808 ...

%e 5 | 10 30 125 720 4040 15550 45395 109840 ...

%e 6 | 20 55 231 1754 15550 114105 526505 1776676 ...

%e 7 | 35 91 385 3654 45395 526505 4662721 24865260 ...

%e 8 | 56 140 596 6808 109840 1776676 24865260 256485936 ...

%e ...

%o (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)

%Y Main diagonal is A360854.

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

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

%K nonn,tabl

%O 1,7

%A _Andrew Howroyd_, Feb 24 2023