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

1, 3, 3, 6, 12, 6, 10, 33, 33, 10, 15, 72, 135, 72, 15, 21, 135, 438, 438, 135, 21, 28, 228, 1140, 2224, 1140, 228, 28, 36, 357, 2511, 8850, 8850, 2511, 357, 36, 45, 528, 4893, 27480, 55725, 27480, 4893, 528, 45, 55, 747, 8700, 70462, 265665, 265665, 70462, 8700, 747, 55

Offset

1,2

Comments

T(m,n) is the number of induced paths including zero length paths in the m X n rook graph. This is also the number of induced trees in these graphs since these are the only induced trees.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Eric Weisstein's World of Mathematics, Complete Bipartite Graph.

Eric Weisstein's World of Mathematics, Graph Path.

Eric Weisstein's World of Mathematics, Rook Graph.

Formula

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

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

Example

Array begins:
===================================================
m\n|  1   2    3     4      5        6        7 ...
---+-----------------------------------------------
1  |  1   3    6    10     15       21       28 ...
2  |  3  12   33    72    135      228      357 ...
3  |  6  33  135   438   1140     2511     4893 ...
4  | 10  72  438  2224   8850    27480    70462 ...
5  | 15 135 1140  8850  55725   265665   962010 ...
6  | 21 228 2511 27480 265665  2006316 11158203 ...
7  | 28 357 4893 70462 962010 11158203 98309827 ...
   ...

Prog

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

Crossrefs

Main diagonal is A288035.

Rows 1..2 are A000217, A054602.

Cf. A360849 (cycles), A360851.

Sequence in context: A326498 A367644 A094305 * A360202 A057963 A250301

Adjacent sequences: A360847 A360848 A360849 * A360851 A360852 A360853

Keyword

nonn,tabl

Author

Andrew Howroyd, Feb 23 2023

Status

approved