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

%I #12 Feb 27 2023 22:51:49

%S 1,3,3,6,12,6,10,33,33,10,15,72,135,72,15,21,135,438,438,135,21,28,

%T 228,1140,2224,1140,228,28,36,357,2511,8850,8850,2511,357,36,45,528,

%U 4893,27480,55725,27480,4893,528,45,55,747,8700,70462,265665,265665,70462,8700,747,55

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

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

%H Andrew Howroyd, <a href="/A360850/b360850.txt">Table of n, a(n) for n = 1..1275</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/GraphPath.html">Graph Path</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=1..min(m,n)} j!^2*binomial(m,j)*binomial(n,j)*(1 + (m+n)/2 - j).

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

%e Array begins:

%e ===================================================

%e m\n| 1 2 3 4 5 6 7 ...

%e ---+-----------------------------------------------

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

%e 2 | 3 12 33 72 135 228 357 ...

%e 3 | 6 33 135 438 1140 2511 4893 ...

%e 4 | 10 72 438 2224 8850 27480 70462 ...

%e 5 | 15 135 1140 8850 55725 265665 962010 ...

%e 6 | 21 228 2511 27480 265665 2006316 11158203 ...

%e 7 | 28 357 4893 70462 962010 11158203 98309827 ...

%e ...

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

%Y Main diagonal is A288035.

%Y Rows 1..2 are A000217, A054602.

%Y Cf. A360849 (cycles), A360851.

%K nonn,tabl

%O 1,2

%A _Andrew Howroyd_, Feb 23 2023