A360851 Array read by antidiagonals: T(m,n) is the number of induced paths in the rook graph K_m X K_n.

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

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

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.

Cf. A003991, A360199, A360850.

Sequence in context: A179450 A333287 A360199 * A117240 A151857 A359200

Adjacent sequences: A360848 A360849 A360850 * A360852 A360853 A360854

Keyword

nonn,tabl

Author

Andrew Howroyd, Feb 24 2023

Status

approved