A291623 Number of maximal irredundant and minimal dominating sets in the n X n rook complement graph.

1, 4, 48, 320, 1610, 6012, 17948, 45488, 101970, 207920, 393272, 699888, 1184378, 1921220, 3006180, 4560032, 6732578, 9706968, 13704320, 18988640, 25872042, 34720268, 45958508, 60077520, 77640050, 99287552, 125747208, 157839248, 196484570, 242712660

Offset: 1

Author

Eric W. Weisstein, Aug 28 2017

Keywords

• nonn

Comments

From Andrew Howroyd, Aug 30 2017: (Start)

For n > 2 the maximal irredundant sets are:

- all vertices in any single row or column,

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

- any vertex with another in the same row and a third in the same column,

- two vertices in each of two rows/columns and none in the same column/row. (End)

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..500
• Eric Weisstein's World of Mathematics, Maximal Irredundant Set
• Eric Weisstein's World of Mathematics, Minimal 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. A291622.

Programs

Mathematica

Table[Piecewise[{{1, n == 1}, {4, n == 2}}, 2 n + 6 Binomial[n, 3]^2 + n^2 (n - 1)^2 + 12 Binomial[n, 4] Binomial[n, 2]], {n, 20}]
Join[{1, 4}, LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {48, 320, 1610, 6012, 17948, 45488, 101970}, 18]]
CoefficientList[Series[(-1 + 3 x - 41 x^2 - 33 x^3 - 273 x^4 + 99 x^5 - 77 x^6 + 27 x^7 - 4 x^8)/(-1 + x)^7, {x, 0, 20}], x]

PARI

a(n) = if(n<3, [1,4][n], (5*n^6 - 33*n^5 + 89*n^4 - 99*n^3 + 38*n^2 + 24*n) / 12); \\ Andrew Howroyd, Aug 30 2017

Formula

From Andrew Howroyd, Aug 30 2017: (Start)

a(n) = 2*n + 6*binomial(n,3)^2 + n^2*(n-1)^2 + 12*binomial(n,4)*binomial(n,2) for n > 2.

a(n) = (5*n^6 - 33*n^5 + 89*n^4 - 99*n^3 + 38*n^2 + 24*n) / 12 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.

G.f.: x*(1 - 3*x + 41*x^2 + 33*x^3 + 273*x^4 - 99*x^5 + 77*x^6 - 27*x^7 + 4*x^8)/(1-x)^7.

(End)

Extensions

Terms a(6) and beyond from Andrew Howroyd, Aug 30 2017