|
|
A360850
|
|
Array read by antidiagonals: T(m,n) is the number of (undirected) paths in the complete bipartite graph K_{m,n}.
|
|
5
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
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
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|