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