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,12

Links

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.

Formula

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

Example

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

Prog

(PARI)
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))}

Crossrefs

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.

Sequence in context: A178143 A070435 A070516 * A143298 A177839 A013669

Adjacent sequences: A384113 A384114 A384115 * A384117 A384118 A384119

Keyword

nonn,tabl

Author

Andrew Howroyd, May 19 2025

Status

approved