login
Array read by antidiagonals: T(m,n) is the number of (undirected) cycles in the complete bipartite graph K_{m,n}.
4

%I #13 Feb 27 2023 22:51:52

%S 0,0,0,0,1,0,0,3,3,0,0,6,15,6,0,0,10,42,42,10,0,0,15,90,204,90,15,0,0,

%T 21,165,660,660,165,21,0,0,28,273,1650,3940,1650,273,28,0,0,36,420,

%U 3486,15390,15390,3486,420,36,0,0,45,612,6552,45150,113865,45150,6552,612,45,0

%N Array read by antidiagonals: T(m,n) is the number of (undirected) cycles in the complete bipartite graph K_{m,n}.

%C Also, T(m,n) is the number of chordless cycles of length >= 4 in the m X n rook graph.

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

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

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

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

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

%F T(m,n) = Sum_{j=2..min(m,n)} binomial(m,j)*binomial(n,j)*j!*(j-1)!/2.

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

%e 2 | 0 1 3 6 10 15 21 28 ...

%e 3 | 0 3 15 42 90 165 273 420 ...

%e 4 | 0 6 42 204 660 1650 3486 6552 ...

%e 5 | 0 10 90 660 3940 15390 45150 109480 ...

%e 6 | 0 15 165 1650 15390 113865 526155 1776180 ...

%e 7 | 0 21 273 3486 45150 526155 4662231 24864588 ...

%e 8 | 0 28 420 6552 109480 1776180 24864588 256485040 ...

%e ...

%e Lower half of array as triangle T(n,k) for 1 <= k <= n begins:

%e 0;

%e 0, 1;

%e 0, 3, 15;

%e 0, 6, 42, 204;

%e 0, 10, 90, 660, 3940;

%e 0, 15, 165, 1650, 15390, 113865;

%e 0, 21, 273, 3486, 45150, 526155, 4662231;

%e ...

%o (PARI) T(m,n) = sum(j=2, min(m,n), binomial(m,j)*binomial(n,j)*j!*(j-1)!/2)

%Y Rows 1..3 are A000004, A000217(n-1), A059270(n-1).

%Y Main diagonal is A070968.

%Y Cf. A269562, A286418, A360850 (paths), A360853.

%K nonn,tabl

%O 1,8

%A _Andrew Howroyd_, Feb 23 2023