A303111 Array read by antidiagonals: T(m,n) = number of total dominating sets in the grid graph P_m X P_n.

0, 1, 1, 3, 9, 3, 4, 25, 25, 4, 5, 81, 161, 81, 5, 9, 289, 961, 961, 289, 9, 16, 961, 6235, 11236, 6235, 961, 16, 25, 3249, 39601, 137641, 137641, 39601, 3249, 25, 39, 11025, 251433, 1677025, 3270375, 1677025, 251433, 11025, 39

Offset

1,4

Comments

Equivalently, the number of n X m binary matrices with every element adjacent to some 0 horizontally or vertically.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..435

Eric Weisstein's World of Mathematics, Grid Graph

Eric Weisstein's World of Mathematics, Total Dominating Set

Example

Table begins:
=======================================================================
m\n|  1    2      3        4          5            6              7
---|-------------------------------------------------------------------
1  |  0    1      3        4          5            9             16 ...
2  |  1    9     25       81        289          961           3249 ...
3  |  3   25    161      961       6235        39601         251433 ...
4  |  4   81    961    11236     137641      1677025       20430400 ...
5  |  5  289   6235   137641    3270375     76405081     1783064069 ...
6  |  9  961  39601  1677025   76405081   3416753209   152598828321 ...
7  | 16 3249 251433 20430400 1783064069 152598828321 13057656650476 ...
...

Crossrefs

Rows 1..2 are A195971(n-1), A141583(n+1).

Main diagonal is A133793.

Cf. A218354 (dominating sets), A291872 (connected dominating sets).

Cf. A303114 (king graph), A303118 (minimal total dominating sets).

Sequence in context: A201416 A072560 A290506 * A299633 A074959 A010632

Adjacent sequences: A303108 A303109 A303110 * A303112 A303113 A303114

Keyword

nonn,tabl

Author

Andrew Howroyd, Apr 18 2018

Status

approved