A347922 Number of minimal total dominating sets in the n X n rook complement graph.

0, 1, 51, 492, 2500, 8925, 25431, 61936, 134352, 266625, 493075, 861036, 1433796, 2293837, 3546375, 5323200, 7786816, 11134881, 15604947, 21479500, 29091300, 38829021, 51143191, 66552432, 85650000, 109110625, 137697651, 172270476, 213792292, 263338125

Offset: 1

Author

Eric W. Weisstein, Sep 19 2021

Keywords

• nonn
• easy

Comments

From Andrew Howroyd, Jan 19 2022: (Start)

The vertex sets which are not totally dominating are just those that are contained in the union of a single row and column. Minimal total dominating sets are:

- any three vertices such that no two are in the same row or column,

- two vertices in each of two rows/columns. (End)

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Minimal Total 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. A292074, A303209, A303212.

Programs

Mathematica

Table[(n - 1)^2 n^2 (5 n^2 - 11 n + 5)/12, {n, 20}] (* Eric W. Weisstein, May 11 2024 *)
LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {0, 1, 51, 492, 2500, 8925, 25431}, 20] (* Eric W. Weisstein, May 11 2024 *)
CoefficientList[Series[-x (1 + 44 x + 156 x^2 + 92 x^3 + 7 x^4)/(-1 + x)^7, {x, 0, 20}], x] (* Eric W. Weisstein, May 11 2024 *)

PARI

a(n) = (5*n^2 - 11*n + 5)*n^2*(n-1)^2/12 \\ Andrew Howroyd, Jan 19 2022

Formula

From Andrew Howroyd, Jan 19 2022: (Start)

a(n) = 6*binomial(n,3)^2 + 2*binomial(n,2)^3 - binomial(n,2)^2.

a(n) = (5*n^2 - 11*n + 5)*n^2*(n-1)^2/12.

G.f.: x*(1 + 44*x + 156*x^2 + 92*x^3 + 7*x^4)/(1 - x)^7.

(End)

Extensions

Terms a(6) and beyond from Andrew Howroyd, Jan 19 2022