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

Author

Eric W. Weisstein, Aug 28 2017

Keywords

• nonn

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

Crossrefs

Cf. A291623.

Programs

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]

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

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)

Extensions

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