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
KEYWORD
nonn
AUTHOR
Eric W. Weisstein, Aug 28 2017
EXTENSIONS
Terms a(6) and beyond from Andrew Howroyd, Aug 30 2017
STATUS
approved