A287063 -id:A287063 - cp's OEIS frontend

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.

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

A384121 Array read by antidiagonals: T(n,m) is the number of 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, 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).

A294140 Number of total dominating sets in the n-crown graph.

Original entry on oeis.org

0, 1, 16, 121, 676, 3249, 14400, 61009, 252004, 1026169, 4145296, 16670889, 66879684, 267944161, 1072693504, 4292739361, 17175150916, 68709515625, 274856935824, 1099467588025, 4397954236900, 17591993106961, 70368341525056, 281474137850481, 1125898162012836

Offset: 1

Eric W. Weisstein, Apr 16 2018

In a total dominating set each side of the crown graph requires any two vertices on the other side to dominate it. - Andrew Howroyd, Apr 16 2018

Eric Weisstein's World of Mathematics, Crown Graph
Eric Weisstein's World of Mathematics, Total Dominating Set
Index entries for linear recurrences with constant coefficients, signature (11,-47,101,-116,68,-16).

Cf. A287063, A287471.

Table[(1 - 2^n + n)^2, {n, 20}]
LinearRecurrence[{11, -47, 101, -116, 68, -16}, {0, 1, 16, 121, 676, 3249}, 20]
CoefficientList[Series[x (1 + 5 x - 8 x^2 - 4 x^3)/((-1 + x)^3 (-1 + 2 x)^2 (-1 + 4 x)), {x, 0, 20}], x]

a(n)=(2^n-1-n)^2; \\ Andrew Howroyd, Apr 16 2018

a(n) = (2^n - 1 - n)^2. - Andrew Howroyd, Apr 16 2018
a(n) = 11*a(n-1) - 47*a(n-2) + 101*a(n-3) - 116*a(n-4) + 68*a(n-5) -16*a(n-6).
G.f.: x^2*(1 + 5*x - 8*x^2 - 4*x^3)/((-1 + x)^3*(-1 + 2*x)^2*(-1 + 4*x)).

a(1)-a(2) and a(11)-a(25) from Andrew Howroyd, Apr 16 2018

cp's OEIS Frontend

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

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

A294140 Number of total dominating sets in the n-crown graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions