login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A287274 Array read by antidiagonals: T(m,n) = number of dominating sets in the lattice (rook) graph K_m X K_n. 5
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 a 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

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

Main diagonal is A287065.

Row 2 is A191341.

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

Sequence in context: A326269 A052989 A252750 * A305099 A292141 A022403

Adjacent sequences:  A287271 A287272 A287273 * A287275 A287276 A287277

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, May 22 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 04:27 EST 2020. Contains 331133 sequences. (Running on oeis4.)