A384118 -id:A384118 - cp's OEIS frontend

A347921 Number of minimal total dominating sets in the n X n rook graph.

0, 4, 51, 368, 7310, 301572, 10893008, 425004288, 21411720954, 1402042079000, 105105019187432, 8635626858155904, 799519643414632478, 84867202351157123016, 10156012624316961798300, 1341516630604157917448192, 194184270583421507775461426, 30809161255439152269369310392

Offset: 1

Eric W. Weisstein, Sep 19 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Minimal Total Dominating Set
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal of A384118.

Cf. A303208, A303211.

a(6)-a(9) from Christian Sievers, Nov 24 2023

a(10) onwards from Andrew Howroyd, May 20 2025

A384116 Array read by antidiagonals: T(n,m) is the number of total dominating sets in the n X m rook graph K_n X K_m.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 4, 9, 4, 1, 1, 11, 39, 39, 11, 1, 1, 26, 183, 334, 183, 26, 1, 1, 57, 833, 3087, 3087, 833, 57, 1, 1, 120, 3629, 27472, 53731, 27472, 3629, 120, 1, 1, 247, 15291, 236127, 922515, 922515, 236127, 15291, 247, 1, 1, 502, 63051, 1975246, 15524639, 30844786, 15524639, 1975246, 63051, 502, 1

Offset: 0

Andrew Howroyd, May 19 2025

			Array begins:
=================================================================
n\m | 0   1     2       3         4           5             6 ...
----+------------------------------------------------------------
  0 | 1   1     1       1         1           1             1 ...
  1 | 1   0     1       4        11          26            57 ...
  2 | 1   1     9      39       183         833          3629 ...
  3 | 1   4    39     334      3087       27472        236127 ...
  4 | 1  11   183    3087     53731      922515      15524639 ...
  5 | 1  26   833   27472    922515    30844786    1019569593 ...
  6 | 1  57  3629  236127  15524639  1019569593   66544564805 ...
  7 | 1 120 15291 1975246 256594143 33329148492 4314985562475 ...
  ...

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

Main diagonal is A303208.
Column 0 is A000012.
Column 1 is A000295(n), n > 0.
Column 2 is A287063(n), n > 1.
Cf. A287274, A384117, A384118.

B(n,m) = {sum(i=0, min(n,m), (-1)^i*binomial(n,i)*binomial(m,i)*i!*(2^(n-i)-1)^(m-i))}
T(n,m) = {B(n,m) - sum(i=1, m, (-1)^i*binomial(m,i)*B(m-i,n))}

T(n,m) = B(n,m) - Sum_{i=1..m} (-1)^i*binomial(m,i)*B(m-i,n), where B(n,m) = Sum_{i=0..m} (-1)^i*binomial(n,i)*binomial(m,i)*i!*(2^(n-i)-1)^(m-i).

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

A384117 Array read by antidiagonals: T(n,m) is the number of minimum total dominating sets in the n X m rook graph K_n X K_m.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 3, 4, 3, 1, 1, 6, 3, 3, 6, 1, 1, 10, 4, 6, 4, 10, 1, 1, 15, 5, 4, 4, 5, 15, 1, 1, 21, 6, 5, 80, 5, 6, 21, 1, 1, 28, 7, 6, 65, 65, 6, 7, 28, 1, 1, 36, 8, 7, 96, 410, 96, 7, 8, 36, 1, 1, 45, 9, 8, 133, 306, 306, 133, 8, 9, 45, 1

Offset: 0

Andrew Howroyd, May 19 2025

For 1 < m <= n, the minimum size of a total dominating set is m. When 1 < m < n, solutions have exactly one vertex in each column. In the special case of n = m, solutions either have exactly one vertex in each column or have exactly one vertex in each row.

			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  0 1 3   6  10   15    21     28 ...
  2 | 1  1 4 3   4   5    6     7      8 ...
  3 | 1  3 3 6   4   5    6     7      8 ...
  4 | 1  6 4 4  80  65   96   133    176 ...
  5 | 1 10 5 5  65 410  306   427    568 ...
  6 | 1 15 6 6  96 306 5112  4207   6448 ...
  7 | 1 21 7 7 133 427 4207 48818  38424 ...
  8 | 1 28 8 8 176 568 6448 38424 695424 ...
  ...

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

Main diagonal is A303211.
Column 0 is A000012.
Column 1 is A000217(n-1), n > 0.
Cf. A384116, A384118, A384119.

B(n,k) = {if(k<=n, if(k==1, binomial(n,2), sum(i=0, k, (-1)^i * binomial(k,i) * binomial(n,i) * i! * (n-i)^(k-i))))}
T(n,m) = {if(n==0&&m==0, 1, B(n,m) + B(m,n))}

T(n,m) = Sum_{i=0..m} (-1)^i * binomial(m,i) * binomial(n,i) * i! * (n-i)^(m-i) for 1 < m < n.
T(n,m) = T(m,n).
T(n,2) = T(n,3) = n for n >= 4.

cp's OEIS Frontend

A347921 Number of minimal total dominating sets in the n X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A384116 Array read by antidiagonals: T(n,m) is the number of total dominating sets in the n X m rook graph K_n X K_m.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A384117 Array read by antidiagonals: T(n,m) is the number of minimum total dominating sets in the n X m rook graph K_n X K_m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula