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

0, 1, 6, 96, 600, 2400, 7350, 18816, 42336, 86400, 163350, 290400, 490776, 794976, 1242150, 1881600, 2774400, 3995136, 5633766, 7797600, 10613400, 14229600, 18818646, 24579456, 31740000, 40560000, 51333750, 64393056, 80110296, 98901600

Offset: 1

Author

Eric W. Weisstein, Apr 19 2018

Keywords

• nonn
• easy

Comments

For n > 2, the minimum total dominating sets are any three vertices such that no two are in the same row or column. - Andrew Howroyd, Apr 20 2018

Essentially the same as A179058(n), differing only for n=2. - Eric W. Weisstein, Dec 06 2023

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Rook Complement Graph.
• Eric Weisstein's World of Mathematics, Minimum Total Dominating Set.
• Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Crossrefs

Cf. A179058, A303209, A347922.

Programs

Mathematica

Table[If[n == 2, 1, 6 Binomial[n, 3]^2], {n, 20}]
Join[{0, 1}, LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {0, 0, 6, 96, 600, 2400, 7350}, {3, 20}]]
CoefficientList[Series[x (-1 + x - 75 x^2 - 19 x^3 - 41 x^4 + 21 x^5 - 7 x^6 + x^7)/(-1 + x)^7, {x, 0, 20}], x]

PARI

a(n) = if(n<3, n==2, 6*binomial(n,3)^2) \\ Andrew Howroyd, Apr 20 2018

PARI

concat(0, Vec(x^2*(1 - x + 75*x^2 + 19*x^3 + 41*x^4 - 21*x^5 + 7*x^6 - x^7) / (1 - x)^7 + O(x^60))) \\ Colin Barker, Apr 20 2018

Formula

a(n) = A179058(n) for n > 2. - Andrew Howroyd, Apr 20 2018

From Colin Barker, Apr 20 2018: (Start)

G.f.: x^2*(1 - x + 75*x^2 + 19*x^3 + 41*x^4 - 21*x^5 + 7*x^6 - x^7) / (1 - x)^7.

a(n) = n^2*(2 - 3*n + n^2)^2 / 6 for n > 2.

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

(End)

Extensions

a(6)-a(30) from Andrew Howroyd, Apr 20 2018