A384845 Array read by antidiagonals: T(n,m) is the number of spanning trees in the n X m rook graph K_n X K_m.

1, 1, 1, 3, 4, 3, 16, 75, 75, 16, 125, 3456, 11664, 3456, 125, 1296, 300125, 5647152, 5647152, 300125, 1296, 16807, 42467328, 6291456000, 34359738368, 6291456000, 42467328, 16807, 262144, 8931928887, 13556617751088, 564859072962000, 564859072962000, 13556617751088, 8931928887, 262144

Offset

1,4

Links

Andrew Howroyd, Table of n, a(n) for n = 1..820 (first 40 antidiagonals)

Eric Weisstein's World of Mathematics, Rook Graph.

Eric Weisstein's World of Mathematics, Spanning Tree.

Formula

T(n,m) = n^(n-2) * m^(m-2) * (n+m)^((n-1)*(m-1)).

Example

Array begins:
=====================================================================
n\m |   1      2          3               4                     5 ...
----+----------------------------------------------------------------
  1 |   1      1          3              16                   125 ...
  2 |   1      4         75            3456                300125 ...
  3 |   3     75      11664         5647152            6291456000 ...
  4 |  16   3456    5647152     34359738368       564859072962000 ...
  5 | 125 300125 6291456000 564859072962000 156250000000000000000 ...
  ...

Prog

(PARI) T(n, m) = n^(n-2) * m^(m-2) * (n+m)^((n-1)*(m-1))

Crossrefs

Main diagonal is A193137.

Columns 1..2 are A000272, A006236.

Sequence in context: A385014 A287199 A384105 * A332830 A288364 A287955

Adjacent sequences: A384842 A384843 A384844 * A384846 A384847 A384848

Keyword

nonn,tabl

Author

Andrew Howroyd, Jun 10 2025

Status

approved