A384120 -id:A384120 - cp's OEIS frontend

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

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 9, 1, 1, 1, 1, 39, 39, 1, 1, 1, 1, 183, 421, 183, 1, 1, 1, 1, 833, 3825, 3825, 833, 1, 1, 1, 1, 3629, 32047, 64727, 32047, 3629, 1, 1, 1, 1, 15291, 260355, 1046425, 1046425, 260355, 15291, 1, 1, 1, 1, 63051, 2092909, 16771879, 33548731, 16771879, 2092909, 63051, 1, 1

Offset: 0

Andrew Howroyd, May 20 2025

Non-dominating sets are just those that are contained in the union of a single row and column minus the intersecting vertex.

			Array begins:
===============================================================
n\m | 0 1     2       3         4           5             6 ...
----+----------------------------------------------------------
  0 | 1 1     1       1         1           1             1 ...
  1 | 1 1     1       1         1           1             1 ...
  2 | 1 1     9      39       183         833          3629 ...
  3 | 1 1    39     421      3825       32047        260355 ...
  4 | 1 1   183    3825     64727     1046425      16771879 ...
  5 | 1 1   833   32047   1046425    33548731    1073727713 ...
  6 | 1 1  3629  260355  16771879  1073727713   68719441881 ...
  7 | 1 1 15291 2092909 268422785 34359704907 4398046428559 ...
  ...

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

Main diagonal is A292073.
Columns 0 and 1 are A000012.
Column 2 is A287063, n > 1.
Cf. A384120 (independent sets), A384122, A384123.

T(n,m) = if(n<=1 || m<=1, 1, 2^(n*m) - n*(2^m-2) - m*(2^n-2) + n*m - n*m*(2^(m-1)-1)*(2^(n-1)-1) + n*(n-1)*m*(m-1)/2 - 1)

T(n,m) = 2^(n*m) - n*(2^m-2) - m*(2^n-2) + n*m - n*m*(2^(m-1)-1)*(2^(n-1)-1) + n*(n-1)*m*(m-1)/2 - 1 for n > 1, m > 1.

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

A288958 Number of cliques in the n X n rook graph.

Original entry on oeis.org

1, 2, 9, 34, 105, 286, 721, 1730, 4017, 9118, 20361, 44914, 98137, 212798, 458529, 982786, 2096865, 4456126, 9436825, 19922546, 41942601, 88079902, 184548849, 385875394, 805305745, 1677720926, 3489660201, 7247756530, 15032384697, 31138511998, 64424508481

Offset: 0

Eric W. Weisstein, Jun 20 2017

Also the number of independent vertex sets in the n X n rook complement graph. - Eric W. Weisstein, Sep 11 2017

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Eric Weisstein's World of Mathematics, Clique
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Rook Complement Graph
Eric Weisstein's World of Mathematics, Rook Graph
Index entries for linear recurrences with constant coefficients, signature (7,-19,25,-16,4).

Main diagonal of A384120.

LinearRecurrence[{7, -19, 25, -16, 4}, {2, 9, 34, 105, 286}, 20]
Table[1 + 2 n (2^n - 1) - n^2, {n, 20}]
CoefficientList[Series[(2 - 5 x + 9 x^2 - 12 x^3 + 4 x^4)/((1 - x)^3 (1 - 2 x)^2), {x, 0, 20}], x]

a(n) = 1 + 2*n*(2^n - 1) - n^2.
a(n) = 7*a(n-1) - 19*a(n-2) + 25*a(n-3) - 16*a(n-4) + 4*a(n-5).
G.f.: (1 - 5*x + 14*x^2 - 16*x^3 + 4*x^4)/((1 - x)^3*(1 - 2*x)^2).

a(0) = 1 prepended by Andrew Howroyd, May 22 2025

A384125 Array read by antidiagonals: T(n,m) is the number of edges in the n X m rook graph K_n X K_m.

Original entry on oeis.org

0, 1, 1, 3, 4, 3, 6, 9, 9, 6, 10, 16, 18, 16, 10, 15, 25, 30, 30, 25, 15, 21, 36, 45, 48, 45, 36, 21, 28, 49, 63, 70, 70, 63, 49, 28, 36, 64, 84, 96, 100, 96, 84, 64, 36, 45, 81, 108, 126, 135, 135, 126, 108, 81, 45, 55, 100, 135, 160, 175, 180, 175, 160, 135, 100, 55

Offset: 1

Andrew Howroyd, May 20 2025

			Array begins:
=======================================
n\m |  1  2   3   4   5   6   7   8 ...
----+----------------------------------
  1 |  0  1   3   6  10  15  21  28 ...
  2 |  1  4   9  16  25  36  49  64 ...
  3 |  3  9  18  30  45  63  84 108 ...
  4 |  6 16  30  48  70  96 126 160 ...
  5 | 10 25  45  70 100 135 175 220 ...
  6 | 15 36  63  96 135 180 231 288 ...
  7 | 21 49  84 126 175 231 294 364 ...
  8 | 28 64 108 160 220 288 364 448 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals)
Eric Weisstein's World of Mathematics, Edge Count.
Eric Weisstein's World of Mathematics, Rook Graph.

Main diagonal is A045991.
Columns 1..6 are A000217(n-1), A000290, A045943, A054000, A269457(n-1), A067707.
Cf. A003991 (number of vertices), A360855 (triangles), A384120 (all cliques).

Table[#*Binomial[m, 2] + m*Binomial[#, 2] &[n - m + 1], {n, 11}, {m, n}] // Flatten (* Michael De Vlieger, May 22 2025 *)

T(n,m) = n*binomial(m,2) + m*binomial(n,2)

T(n,m) = n*binomial(m,2) + m*binomial(n,2).
T(n,m) = binomial(n*m,2) - 2*binomial(n,2)*binomial(m,2).
T(n,m) = T(m,n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A288958 Number of cliques in the n X n rook graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A384125 Array read by antidiagonals: T(n,m) is the number of edges in the n X m rook graph K_n X K_m.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula