A291623 - OEIS

%I #20 Sep 04 2021 20:08:45

%S 1,4,48,320,1610,6012,17948,45488,101970,207920,393272,699888,1184378,

%T 1921220,3006180,4560032,6732578,9706968,13704320,18988640,25872042,

%U 34720268,45958508,60077520,77640050,99287552,125747208,157839248,196484570,242712660

%N Number of maximal irredundant and minimal dominating sets in the n X n rook complement graph.

%C From _Andrew Howroyd_, Aug 30 2017: (Start)

%C For n > 2 the maximal irredundant sets are:

%C   - all vertices in any single row or column,

%C   - any three vertices such that no two are in the same row or column,

%C   - any vertex with another in the same row and a third in the same column,

%C   - two vertices in each of two rows/columns and none in the same column/row. (End)

%H Andrew Howroyd, <a href="/A291623/b291623.txt">Table of n, a(n) for n = 1..500</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIrredundantSet.html">Maximal Irredundant Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalDominatingSet.html">Minimal Dominating Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RookComplementGraph.html">Rook Complement Graph</a>

%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (7, -21, 35, -35, 21, -7, 1).

%F From _Andrew Howroyd_, Aug 30 2017: (Start)

%F a(n) = 2*n + 6*binomial(n,3)^2 + n^2*(n-1)^2 + 12*binomial(n,4)*binomial(n,2) for n > 2.

%F a(n) = (5*n^6 - 33*n^5 + 89*n^4 - 99*n^3 + 38*n^2 + 24*n) / 12 for n > 2.

%F 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.

%F 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.

%F (End)

%t 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}]

%t Join[{1, 4}, LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {48, 320, 1610, 6012, 17948, 45488, 101970}, 18]]

%t 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]

%o (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

%Y Cf. A291622.

%K nonn

%O 1,2

%A _Eric W. Weisstein_, Aug 28 2017

%E Terms a(6) and beyond from _Andrew Howroyd_, Aug 30 2017