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
Examples
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 ... ...
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.
Crossrefs
Programs
-
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))}
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.
Comments