A384121 Array read by antidiagonals: T(n,m) is the number of dominating sets in the n X m rook complement graph.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9, 1, 1, 1, 1, 39, 39, 1, 1, 1, 1, 183, 421, 183, 1, 1, 1, 1, 833, 3825, 3825, 833, 1, 1, 1, 1, 3629, 32047, 64727, 32047, 3629, 1, 1, 1, 1, 15291, 260355, 1046425, 1046425, 260355, 15291, 1, 1, 1, 1, 63051, 2092909, 16771879, 33548731, 16771879, 2092909, 63051, 1, 1

Offset: 0

Author

Andrew Howroyd, May 20 2025

Keywords

• nonn
• tabl

Comments

Non-dominating sets are just those that are contained in the union of a single row and column minus the intersecting vertex.

Examples

			Array begins:
===============================================================
n\m | 0 1     2       3         4           5             6 ...
----+----------------------------------------------------------
  0 | 1 1     1       1         1           1             1 ...
  1 | 1 1     1       1         1           1             1 ...
  2 | 1 1     9      39       183         833          3629 ...
  3 | 1 1    39     421      3825       32047        260355 ...
  4 | 1 1   183    3825     64727     1046425      16771879 ...
  5 | 1 1   833   32047   1046425    33548731    1073727713 ...
  6 | 1 1  3629  260355  16771879  1073727713   68719441881 ...
  7 | 1 1 15291 2092909 268422785 34359704907 4398046428559 ...
  ...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)
• Eric Weisstein's World of Mathematics, Dominating Set.
• Eric Weisstein's World of Mathematics, Rook Complement Graph.

Crossrefs

Main diagonal is A292073.

Columns 0 and 1 are A000012.

Column 2 is A287063, n > 1.

Cf. A384120 (independent sets), A384122, A384123.

Programs

PARI

T(n,m) = if(n<=1 || m<=1, 1, 2^(n*m) - n*(2^m-2) - m*(2^n-2) + n*m - n*m*(2^(m-1)-1)*(2^(n-1)-1) + n*(n-1)*m*(m-1)/2 - 1)

Formula

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

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