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,2

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

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)

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]

Prog

(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

Crossrefs

Cf. A291622.

Sequence in context: A274729 A217153 A129002 * A144704 A091904 A192831

Adjacent sequences: A291620 A291621 A291622 * A291624 A291625 A291626

Keyword

nonn

Author

Eric W. Weisstein, Aug 28 2017

Extensions

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

Status

approved