A384123 -id:A384123 - 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).

A384122 Array read by antidiagonals: T(n,m) is the number of minimum 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, 3, 3, 1, 1, 1, 1, 4, 48, 4, 1, 1, 1, 1, 5, 100, 100, 5, 1, 1, 1, 1, 6, 185, 240, 185, 6, 1, 1, 1, 1, 7, 306, 480, 480, 306, 7, 1, 1, 1, 1, 8, 469, 840, 1000, 840, 469, 8, 1, 1, 1, 1, 9, 680, 1344, 1800, 1800, 1344, 680, 9, 1, 1

Offset: 0

Andrew Howroyd, May 20 2025

For n >= 3, m >= 3, the minimum size of a dominating set is 3.

			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   3    4    5    6     7     8 ...
  3 | 1 1 3  48  100  185  306   469   680 ...
  4 | 1 1 4 100  240  480  840  1344  2016 ...
  5 | 1 1 5 185  480 1000 1800  2940  4480 ...
  6 | 1 1 6 306  840 1800 3300  5460  8400 ...
  7 | 1 1 7 469 1344 2940 5460  9114 14112 ...
  8 | 1 1 8 680 2016 4480 8400 14112 21952 ...
   ...

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

Main diagonal is A292074.
Column 3 is A090197(n-1), n >= 4.
Column 4 is A272871(n), n >= 4.
Cf. A384121, A384123.

T(n,m) = if(n<=2||m<=2, if(n<=1||m<=1, 1, if(n==2,m)+if(m==2,n)), 4*binomial(n,2)*binomial(m,2) + 6*binomial(n,3)*binomial(m,3) + if(n==3,m) + if(m==3,n))

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

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

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula