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.

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

Comments

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.

Links

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.

Formula

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.

Example

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

Prog

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

Crossrefs

Main diagonal is A303211.

Column 0 is A000012.

Column 1 is A000217(n-1), n > 0.

Cf. A384116, A384118, A384119.

Sequence in context: A096646 A306234 A290057 * A384118 A249790 A302713

Adjacent sequences: A384114 A384115 A384116 * A384118 A384119 A384120

Keyword

nonn,tabl

Author

Andrew Howroyd, May 19 2025

Status

approved