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

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 3, 3, 1, 1, 1, 1, 4, 48, 4, 1, 1, 1, 1, 5, 100, 100, 5, 1, 1, 1, 1, 6, 185, 240, 185, 6, 1, 1, 1, 1, 7, 306, 480, 480, 306, 7, 1, 1, 1, 1, 8, 469, 840, 1000, 840, 469, 8, 1, 1, 1, 1, 9, 680, 1344, 1800, 1800, 1344, 680, 9, 1, 1

Offset: 0

Author

Andrew Howroyd, May 20 2025

Keywords

• nonn
• tabl

Comments

For n >= 3, m >= 3, the minimum size of a dominating set is 3.

Examples

			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 1   1    1    1    1     1     1 ...
  2 | 1 1 4   3    4    5    6     7     8 ...
  3 | 1 1 3  48  100  185  306   469   680 ...
  4 | 1 1 4 100  240  480  840  1344  2016 ...
  5 | 1 1 5 185  480 1000 1800  2940  4480 ...
  6 | 1 1 6 306  840 1800 3300  5460  8400 ...
  7 | 1 1 7 469 1344 2940 5460  9114 14112 ...
  8 | 1 1 8 680 2016 4480 8400 14112 21952 ...
   ...
		

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 Complement Graph.

Crossrefs

Main diagonal is A292074.

Column 3 is A090197(n-1), n >= 4.

Column 4 is A272871(n), n >= 4.

Cf. A384121, A384123.

Programs

PARI

T(n,m) = if(n<=2||m<=2, if(n<=1||m<=1, 1, if(n==2,m)+if(m==2,n)), 4*binomial(n,2)*binomial(m,2) + 6*binomial(n,3)*binomial(m,3) + if(n==3,m) + if(m==3,n))

Formula

T(n,m) = 4*binomial(n,2)*binomial(m,2) + 6*binomial(n,3)*binomial(m,3) for n >= 4, m >= 4.

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

T(n,0) = T(n,1) = 1.