A291622 Number of irredundant sets in the n X n rook complement graph.

2, 9, 94, 777, 3286, 10771, 29366, 69873, 149950, 297111, 553114, 980953, 1677014, 2793771, 4584286, 7492065, 12335422, 20688751, 35673698, 63602601, 117391702, 223644675, 437338630, 872239057, 1763820926, 3599298951, 7386070186, 15205369593, 31353128470

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

Cf. A291623.

Sequence in context: A365363 A011804 A292467 * A058156 A011837 A106343

Adjacent sequences: A291619 A291620 A291621 * A291623 A291624 A291625

Keyword

nonn

Author

Eric W. Weisstein, Aug 28 2017

Extensions

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

Status

approved