A291623 -id:A291623 - cp's OEIS frontend

A292073 Number of dominating sets in the n X n rook complement graph.

1, 9, 421, 64727, 33548731, 68719441881, 562949953225997, 18446744073708516927, 2417851639229258344138819, 1267650600228229401496677076985, 2658455991569831745807614120434020301, 22300745198530623141535718272648360902500919

Offset: 1

Eric W. Weisstein, Sep 12 2017

nonn

Non-dominating sets are just those that are contained in the union of a single row and column minus the intersecting vertex. - Andrew Howroyd, Sep 13 2017

Vincenzo Librandi, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Dominating Set
Eric Weisstein's World of Mathematics, Rook Complement Graph

Cf. A291623, A292074.

[1] cat [2^(n^2)-2*n*(2^n-2)+n^2-n^2*(2^(n-1)-1)^2+ n^2*(n-1)^2-2*Binomial(n,2)^2-1: n in [2..15]]; // Vincenzo Librandi, Mar 17 2018

Table[If[n == 1, 1, 2^n^2 + (2^n (n - 2) - 4^(n - 1) n + (n - 1)^2 n/2 + 4) n - 1], {n, 20}]

a(n) = if(n == 1, 1, 2^(n^2) - 2*n*(2^n - 2) + n^2 - n^2*(2^(n-1)-1)^2 + n^2*(n-1)^2 - 2*binomial(n,2)^2 - 1); \\ Andrew Howroyd, Sep 13 2017

a(n) = 2^(n^2) - 2*n*(2^n - 2) + n^2 - n^2*(2^(n-1)-1)^2 + n^2*(n-1)^2 - 2*binomial(n,2)^2 - 1 for n > 1. - Andrew Howroyd, Sep 13 2017

a(6)-a(12) from Andrew Howroyd, Sep 13 2017

A292074 Number of minimum dominating sets in the n X n rook complement graph.

Original entry on oeis.org

1, 4, 48, 240, 1000, 3300, 9114, 21952, 47520, 94500, 175450, 307824, 515112, 828100, 1286250, 1939200, 2848384, 4088772, 5750730, 7942000, 10789800, 14443044, 19074682, 24884160, 32100000, 40982500, 51826554, 64964592, 80769640, 99658500, 122095050

Offset: 1

Eric W. Weisstein, Sep 12 2017

The minimum dominating sets are the minimal dominating sets (A291623) of size equal to the domination number. For n > 2, the domination number is 3. For n > 3, the minimal dominating sets of size 3 are either any three vertices such that no two are in the same row or column or any vertex with another in the same row and a third in the same column. For n = 3, the case of all vertices in a single row or column also needs to be included. - Andrew Howroyd, Sep 13 2017

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Minimum 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. A291623, A292073.

Join[{1, 4, 48}, LinearRecurrence[{7, -21, 35, -35, 21, -7, 1}, {240, 1000, 3300, 9114, 21952, 47520, 94500}, 20]]
Table[Piecewise[{{1, n == 1}, {48, n == 3}}, 6 Binomial[n, 3]^2 + n^2 (n - 1)^2], {n, 20}]
CoefficientList[Series[(-1 + 3 x - 41 x^2 + 47 x^3 - 223 x^4 + 221 x^5 - 217 x^6 + 127 x^7 - 42 x^8 + 6 x^9)/(-1 + x)^7, {x, 0, 20}], x]

a(n) = if(n<4, [1,4,48][n], 6*binomial(n, 3)^2 + n^2*(n-1)^2); \\ Andrew Howroyd, Sep 13 2017

G.f.: x*(-1 + 3*x - 41*x^2 + 47*x^3 - 223*x^4 + 221*x^5 - 217*x^6 + 127*x^7 - 42*x^8 + 6*x^9)/(-1 + x)^7.
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 > 10.
a(n) = 6*binomial(n, 3)^2 + n^2*(n-1)^2 for n > 3. - Andrew Howroyd, Sep 13 2017

Terms a(6) and beyond from Andrew Howroyd, Sep 13 2017

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

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 5, 5, 1, 1, 1, 1, 12, 48, 12, 1, 1, 1, 1, 37, 121, 121, 37, 1, 1, 1, 1, 98, 278, 320, 278, 98, 1, 1, 1, 1, 219, 579, 729, 729, 579, 219, 1, 1, 1, 1, 430, 1102, 1480, 1610, 1480, 1102, 430, 1, 1, 1, 1, 767, 1943, 2741, 3161, 3161, 2741, 1943, 767, 1, 1

Offset: 0

Andrew Howroyd, May 20 2025

For n > 2, m > 2, the minimal dominating 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.
Except for (n,m) = (2,3) or (3,2), also the number of maximal irredundant sets in the n X m rook complement graph. In particular, there are 11 maximal irredundant sets in these two graphs.

			Array begins:
===================================================
n\m | 0 1   2    3    4    5     6     7     8 ...
----+---------------------------------------------
  0 | 1 1   1    1    1    1     1     1     1 ...
  1 | 1 1   1    1    1    1     1     1     1 ...
  2 | 1 1   4    5   12   37    98   219   430 ...
  3 | 1 1   5   48  121  278   579  1102  1943 ...
  4 | 1 1  12  121  320  729  1480  2741  4716 ...
  5 | 1 1  37  278  729 1610  3161  5682  9533 ...
  6 | 1 1  98  579 1480 3161  6012 10513 17234 ...
  7 | 1 1 219 1102 2741 5682 10513 17948 28827 ...
  8 | 1 1 430 1943 4716 9533 17234 28827 45488 ...
   ...
The T(2,3) = 5 minimal dominating sets are those that contain all vertices in either a single row or a single column. There are also 6 maximal irredundant sets that are not dominating. These are those that contain one vertex in each of the two rows but not in the same column.

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)
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.

Main diagonal is A291623.
Columns 0 and 1 are A000012.
Column 2 is A289121 for n > 1.
Cf. A384121, A384122.

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

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

T(n,m) = T(m,n).

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

Original entry on oeis.org

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

Eric W. Weisstein, Aug 28 2017

nonn

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

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

Cf. A291623.

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]

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

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)

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

cp's OEIS Frontend

A292073 Number of dominating sets in the n X n rook complement graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

A292074 Number of minimum dominating sets in the n X n rook complement graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions