|
| |
|
|
A287274
|
|
Array read by antidiagonals: T(m,n) = number of dominating sets in the lattice (rook) graph K_m X K_n.
|
|
7
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
