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,8

Comments

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

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.

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).

Example

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;
  ...

Prog

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

Crossrefs

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

Main diagonal is A070968.

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

Sequence in context: A299554 A300175 A129533 * A155999 A338034 A299904

Adjacent sequences: A360846 A360847 A360848 * A360850 A360851 A360852

Keyword

nonn,tabl

Author

Andrew Howroyd, Feb 23 2023

Status

approved