A384119 Array read by antidiagonals: T(n,m) is the number of minimum dominating sets in the n X m rook graph K_n X K_m.

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 3, 6, 3, 1, 1, 4, 9, 9, 4, 1, 1, 5, 16, 48, 16, 5, 1, 1, 6, 25, 64, 64, 25, 6, 1, 1, 7, 36, 125, 488, 125, 36, 7, 1, 1, 8, 49, 216, 625, 625, 216, 49, 8, 1, 1, 9, 64, 343, 1296, 6130, 1296, 343, 64, 9, 1, 1, 10, 81, 512, 2401, 7776, 7776, 2401, 512, 81, 10, 1

Offset

0,8

Comments

For m <= n, the minimum size of a dominating set is m. When m < n, solutions have exactly one vertex in each column. In the special case of n = m, solutions either have exactly one vertex in each column or have exactly one vertex in each row.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)

Eric Weisstein's World of Mathematics, Minimum Dominating Set.

Eric Weisstein's World of Mathematics, Rook Graph.

Formula

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

T(n,m) = n^m for m < n.

Example

Array begins:
=======================================================
n\m | 0 1  2   3    4     5      6       7        8 ...
----+--------------------------------------------------
  0 | 1 1  1   1    1     1      1       1        1 ...
  1 | 1 1  2   3    4     5      6       7        8 ...
  2 | 1 2  6   9   16    25     36      49       64 ...
  3 | 1 3  9  48   64   125    216     343      512 ...
  4 | 1 4 16  64  488   625   1296    2401     4096 ...
  5 | 1 5 25 125  625  6130   7776   16807    32768 ...
  6 | 1 6 36 216 1296  7776  92592  117649   262144 ...
  7 | 1 7 49 343 2401 16807 117649 1642046  2097152 ...
  8 | 1 8 64 512 4096 32768 262144 2097152 33514112 ...
  ...

Prog

(PARI) T(n, m) = {if(n<=m, m^n) + if(m<=n, n^m) - if(m==n, n!)}

Crossrefs

Main diagonal is A248744.

Cf. A079901, A287274, A290632.

Sequence in context: A008302 A131791 A308497 * A010358 A155865 A156133

Adjacent sequences: A384116 A384117 A384118 * A384120 A384121 A384122

Keyword

nonn,tabl

Author

Andrew Howroyd, May 20 2025

Status

approved