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