login
A360851
Array read by antidiagonals: T(m,n) is the number of induced paths in the rook graph K_m X K_n.
6
0, 1, 1, 3, 8, 3, 6, 27, 27, 6, 10, 64, 126, 64, 10, 15, 125, 426, 426, 125, 15, 21, 216, 1125, 2208, 1125, 216, 21, 28, 343, 2493, 8830, 8830, 2493, 343, 28, 36, 512, 4872, 27456, 55700, 27456, 4872, 512, 36, 45, 729, 8676, 70434, 265635, 265635, 70434, 8676, 729, 45
OFFSET
1,4
COMMENTS
Paths of length zero are not counted here.
LINKS
Eric Weisstein's World of Mathematics, Rook Graph.
Wikipedia, Induced path.
FORMULA
T(m,n) = A360850(m,n) - A003991(m,n).
T(m,n) = -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 | 0 1 3 6 10 15 21 ...
2 | 1 8 27 64 125 216 343 ...
3 | 3 27 126 426 1125 2493 4872 ...
4 | 6 64 426 2208 8830 27456 70434 ...
5 | 10 125 1125 8830 55700 265635 961975 ...
6 | 15 216 2493 27456 265635 2006280 11158161 ...
7 | 21 343 4872 70434 961975 11158161 98309778 ...
...
PROG
(PARI) T(m, n) = sum(j=1, min(m, n), j!^2*binomial(m, j)*binomial(n, j)*(1 + (m+n)/2 - j)) - m*n
CROSSREFS
Main diagonal is A360852.
Rows 1..2 are A000217(n-1), A000578.
Sequence in context: A179450 A333287 A360199 * A117240 A151857 A359200
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Feb 24 2023
STATUS
approved