A292074 Number of minimum dominating sets in the n X n rook complement graph.

1, 4, 48, 240, 1000, 3300, 9114, 21952, 47520, 94500, 175450, 307824, 515112, 828100, 1286250, 1939200, 2848384, 4088772, 5750730, 7942000, 10789800, 14443044, 19074682, 24884160, 32100000, 40982500, 51826554, 64964592, 80769640, 99658500, 122095050

Offset: 1

Author

Eric W. Weisstein, Sep 12 2017

Keywords

• nonn
• easy

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).

Crossrefs

Cf. A291623, A292073.

Programs

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]

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

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

Extensions

Terms a(6) and beyond from Andrew Howroyd, Sep 13 2017