A287274 Array read by antidiagonals: T(m,n) = number of dominating sets in the lattice (rook) graph K_m X K_n.

1, 3, 3, 7, 11, 7, 15, 51, 51, 15, 31, 227, 421, 227, 31, 63, 963, 3615, 3615, 963, 63, 127, 3971, 30517, 59747, 30517, 3971, 127, 255, 16131, 252231, 989295, 989295, 252231, 16131, 255, 511, 65027, 2054941, 16219187, 32260381, 16219187, 2054941, 65027, 511

Offset: 1

Author

Andrew Howroyd, May 22 2017

Keywords

• nonn
• tabl

Comments

A set of vertices can be represented as an m X n binary matrix. If all rows contain at least one 1 then regardless of what is in each row the set will form a dominating set giving (2^n-1)^m solutions. Otherwise if only iA183109(i,n) solutions.

Examples

			Array begins:
=============================================================================
m\n|   1     2       3         4           5             6               7
---|-------------------------------------------------------------------------
1  |   1     3       7        15          31            63             127...
2  |   3    11      51       227         963          3971           16131...
3  |   7    51     421      3615       30517        252231         2054941...
4  |  15   227    3615     59747      989295      16219187       263425695...
5  |  31   963   30517    989295    32260381    1048220463     33884452717...
6  |  63  3971  252231  16219187  1048220463   67680006971   4358402146791...
7  | 127 16131 2054941 263425695 33884452717 4358402146791 559876911043381...
...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..780
• Stephan Mertens, Domination Polynomial of the Rook Graph, JIS 27 (2024) 24.3.7; arXiv:2401.00716 [math.CO], 2024.
• Eric Weisstein's World of Mathematics, Dominating Set
• Eric Weisstein's World of Mathematics, Rook Graph

Crossrefs

Main diagonal is A287065.

Row 2 is A191341.

Cf. A183109, A088699 (independent vertex sets), A290632.

Programs

Mathematica

b[m_, n_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}];
a[m_, n_] := (2^n - 1)^m + Sum[ b[i, n]*Binomial[m, i], {i, 1, m - 1}];
Table[a[m - n + 1, n], {m, 1, 9}, {n, 1, m}] // Flatten (* Jean-François Alcover, Jun 12 2017, adapted from PARI *)

PARI

b(m,n)=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
a(m,n)=(2^n-1)^m + sum(i=1,m-1,b(i,n)*binomial(m,i));
for (i=1,7,for(j=1,7, print1(a(i,j), ",")); print);

Formula

T(m, n) = (2^n-1)^m + Sum_{i=1..m-1} binomial(m,i) * A183109(i,n).