OFFSET
1,2
COMMENTS
The minimum dominating sets are the minimal dominating sets (A291623) of size equal to the domination number. For n > 2, the domination number is 3. For n > 3, the minimal dominating sets of size 3 are either any three vertices such that no two are in the same row or column or any vertex with another in the same row and a third in the same column. For n = 3, the case of all vertices in a single row or column also needs to be included. - Andrew Howroyd, Sep 13 2017
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Minimum Dominating Set
Eric Weisstein's World of Mathematics, Rook Complement Graph
Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).
FORMULA
G.f.: x*(-1 + 3*x - 41*x^2 + 47*x^3 - 223*x^4 + 221*x^5 - 217*x^6 + 127*x^7 - 42*x^8 + 6*x^9)/(-1 + x)^7.
a(n) = 7*a(n-1) - 21*a(n-2) + 35*a(n-3) - 35*a(n-4) + 21*a(n-5) - 7*a(n-6) + a(n-7) for n > 10.
a(n) = 6*binomial(n, 3)^2 + n^2*(n-1)^2 for n > 3. - Andrew Howroyd, Sep 13 2017
MATHEMATICA
Join[{1, 4, 48}, LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {240, 1000, 3300, 9114, 21952, 47520, 94500}, 20]]
Table[Piecewise[{{1, n == 1}, {48, n == 3}}, 6 Binomial[n, 3]^2 + n^2 (n - 1)^2], {n, 20}]
CoefficientList[Series[(-1 + 3 x - 41 x^2 + 47 x^3 - 223 x^4 + 221 x^5 - 217 x^6 + 127 x^7 - 42 x^8 + 6 x^9)/(-1 + x)^7, {x, 0, 20}], x]
PROG
(PARI) a(n) = if(n<4, [1, 4, 48][n], 6*binomial(n, 3)^2 + n^2*(n-1)^2); \\ Andrew Howroyd, Sep 13 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Eric W. Weisstein, Sep 12 2017
EXTENSIONS
Terms a(6) and beyond from Andrew Howroyd, Sep 13 2017
STATUS
approved