A291622 -id:A291622 - cp's OEIS frontend

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

1, 4, 48, 320, 1610, 6012, 17948, 45488, 101970, 207920, 393272, 699888, 1184378, 1921220, 3006180, 4560032, 6732578, 9706968, 13704320, 18988640, 25872042, 34720268, 45958508, 60077520, 77640050, 99287552, 125747208, 157839248, 196484570, 242712660

Offset: 1

Eric W. Weisstein, Aug 28 2017

nonn

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)

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

Cf. A291622.

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]

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

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)

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

A384124 Array read by antidiagonals: T(n,m) is the number of irredundant sets in the n X m rook complement graph.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 8, 9, 8, 1, 1, 16, 24, 24, 16, 1, 1, 32, 77, 94, 77, 32, 1, 1, 64, 178, 284, 284, 178, 64, 1, 1, 128, 373, 624, 777, 624, 373, 128, 1, 1, 256, 724, 1234, 1620, 1620, 1234, 724, 256, 1, 1, 512, 1331, 2258, 3049, 3286, 3049, 2258, 1331, 512, 1

Offset: 0

Andrew Howroyd, May 22 2025

			Array begins:
===============================================
n\m | 0   1   2    3    4     5     6     7 ...
----+------------------------------------------
  0 | 1   1   1    1    1     1     1     1 ...
  1 | 1   2   4    8   16    32    64   128 ...
  2 | 1   4   9   24   77   178   373   724 ...
  3 | 1   8  24   94  284   624  1234  2258 ...
  4 | 1  16  77  284  777  1620  3049  5332 ...
  5 | 1  32 178  624 1620  3286  6022 10268 ...
  6 | 1  64 373 1234 3049  6022 10771 17962 ...
  7 | 1 128 724 2258 5332 10268 17962 29366 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)
Eric Weisstein's World of Mathematics, Irredundant Set.
Eric Weisstein's World of Mathematics, Rook Complement Graph.

Main diagonal is A291622.
Columns 0..2 are A000012, A000079, A290710.
Cf. A384123.

T(n,m) = {n*(2^m-1) + m*(2^n-1) - n*m + if(n>2&&m>2,6,if(n+m>4, 2))*binomial(n,2)*binomial(m,2) + 6*binomial(n,3)*binomial(m,3) + if(m>3,6*binomial(n,2)*binomial(m,3)) + if(n>3,6*binomial(n,3)*binomial(m,2)) + 6*binomial(n,4)*binomial(m,2) + 6*binomial(n,2)*binomial(m,4) + 1}

T(n,m) = n*(2^m-1) + m*(2^n-1) - n*m + binomial(n,2)*binomial(m,2) + 6*binomial(n,3)*binomial(m,3) + 6*binomial(n,2)*binomial(m,3) + 6*binomial(n,3)*binomial(m,2) + 6*binomial(n,4)*binomial(m,2) + 6*binomial(n,2)*binomial(m,4) + 1 for n >= 4, m >= 4.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions