OFFSET
1,2
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 i<m rows contain at least one 1 then all columns must contain a 1 for the set to form a dominating set giving A183109(i,n) solutions.
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
FORMULA
T(m, n) = (2^n-1)^m + Sum_{i=1..m-1} binomial(m,i) * A183109(i,n).
EXAMPLE
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...
...
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 *)
PROG
(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);
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, May 22 2017
STATUS
approved