OFFSET
1,1
COMMENTS
The irredundant sets are the distinct subsets of the maximal irredundant sets. These are either any subset of vertices in a single row or column or otherwise have cardinality of at most four (see A291623). - Andrew Howroyd, Aug 30 2017
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Irredundant Set
Eric Weisstein's World of Mathematics, Rook Complement Graph
Index entries for linear recurrences with constant coefficients, signature (11,-53,147,-259,301,-231,113,-32,4).
FORMULA
From Andrew Howroyd, Aug 30 2017: (Start)
a(n) = 2*n*(2^n) + (5*n^6 - 21*n^5 + 47*n^4 - 51*n^3 + 8*n^2 - 24*n + 12)/12 for n > 3.
a(n) = 11*a(n-1) - 53*a(n-2) + 147*a(n-3) - 259*a(n-4) + 301*a(n-5) - 231*a(n-6) + 113*a(n-7) - 32*a(n-8) + 4*a(n-9) for n > 12.
G.f.: x*(2 - 13*x + 101*x^2 - 74*x^3 - 1084*x^4 + 3717*x^5 - 7077*x^6 + 9470*x^7 - 7634*x^8 + 3876*x^9 - 1128*x^10 + 144*x^11)/((1 - x)^7*(1 - 2*x)^2). (End)
MATHEMATICA
Table[Piecewise[{{9, n == 2}, {94, n == 3}}, 2 n (2^n) + (5 n^6 - 21 n^5 + 47 n^4 - 51 n^3 + 8 n^2 - 24 n + 12)/12], {n, 20}]
Join[{2, 9, 94}, LinearRecurrence[{11, -53, 147, -259, 301, -231, 113, -32, 4}, {777, 3286, 10771, 29366, 69873, 149950, 297111, 553114, 980953}, 20]]
CoefficientList[Series[(2 - 13 x + 101 x^2 - 74 x^3 - 1084 x^4 + 3717 x^5 - 7077 x^6 + 9470 x^7 - 7634 x^8 + 3876 x^9 - 1128 x^10 + 144 x^11)/((1 - x)^7 (1 - 2 x)^2), {x, 0, 20}], x]
PROG
(PARI) a(n) = if(n<4, [2, 9, 94][n], 2*n*(2^n) + (5*n^6 - 21*n^5 + 47*n^4 - 51*n^3 + 8*n^2 - 24*n + 12)/12); \\ Andrew Howroyd, Aug 30 2017
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Eric W. Weisstein, Aug 28 2017
EXTENSIONS
Terms a(6) and beyond from Andrew Howroyd, Aug 30 2017
STATUS
approved