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

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, 21, 165, 660, 660, 165, 21, 0, 0, 28, 273, 1650, 3940, 1650, 273, 28, 0, 0, 36, 420, 3486, 15390, 15390, 3486, 420, 36, 0, 0, 45, 612, 6552, 45150, 113865, 45150, 6552, 612, 45, 0

Offset: 1

Author

Andrew Howroyd, Feb 23 2023

Keywords

• nonn
• tabl

Comments

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

Examples

			Array begins:
========================================================
m\n| 1  2   3    4      5       6        7         8 ...
---+----------------------------------------------------
1  | 0  0   0    0      0       0        0         0 ...
2  | 0  1   3    6     10      15       21        28 ...
3  | 0  3  15   42     90     165      273       420 ...
4  | 0  6  42  204    660    1650     3486      6552 ...
5  | 0 10  90  660   3940   15390    45150    109480 ...
6  | 0 15 165 1650  15390  113865   526155   1776180 ...
7  | 0 21 273 3486  45150  526155  4662231  24864588 ...
8  | 0 28 420 6552 109480 1776180 24864588 256485040 ...
  ...
Lower half of array as triangle T(n,k) for 1 <= k <= n begins:
  0;
  0,  1;
  0,  3,  15;
  0,  6,  42,  204;
  0, 10,  90,  660,  3940;
  0, 15, 165, 1650, 15390, 113865;
  0, 21, 273, 3486, 45150, 526155, 4662231;
  ...
		

Links

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

Crossrefs

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

Main diagonal is A070968.

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

Programs

PARI

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

Formula

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

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