A384123 Array read by antidiagonals: T(n,m) is the number of minimal dominating sets in the n X m rook complement graph.
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 5, 5, 1, 1, 1, 1, 12, 48, 12, 1, 1, 1, 1, 37, 121, 121, 37, 1, 1, 1, 1, 98, 278, 320, 278, 98, 1, 1, 1, 1, 219, 579, 729, 729, 579, 219, 1, 1, 1, 1, 430, 1102, 1480, 1610, 1480, 1102, 430, 1, 1, 1, 1, 767, 1943, 2741, 3161, 3161, 2741, 1943, 767, 1, 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 1 1 1 1 1 1 1 1 ... 2 | 1 1 4 5 12 37 98 219 430 ... 3 | 1 1 5 48 121 278 579 1102 1943 ... 4 | 1 1 12 121 320 729 1480 2741 4716 ... 5 | 1 1 37 278 729 1610 3161 5682 9533 ... 6 | 1 1 98 579 1480 3161 6012 10513 17234 ... 7 | 1 1 219 1102 2741 5682 10513 17948 28827 ... 8 | 1 1 430 1943 4716 9533 17234 28827 45488 ... ... The T(2,3) = 5 minimal dominating sets are those that contain all vertices in either a single row or a single column. There are also 6 maximal irredundant sets that are not dominating. These are those that contain one vertex in each of the two rows but not in the same column.
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..1325 (first 51 antidiagonals)
- Eric Weisstein's World of Mathematics, Maximal Irredundant Set.
- Eric Weisstein's World of Mathematics, Minimal Dominating Set.
- Eric Weisstein's World of Mathematics, Rook Complement Graph.
Crossrefs
Programs
-
PARI
T(n,m) = {if(n<=1||m<=1, 1, n + m + 6*binomial(n,3)*binomial(m,3) + if(n > 2 && m > 2, n*(n-1)*m*(m-1)) + 6*binomial(n,4)*binomial(m,2) + 6*binomial(n,2)*binomial(m,4))}
Formula
T(n,m) = n + m + 6*binomial(n,3)*binomial(m,3) + n*(n-1)*m*(m-1) + 6*binomial(n,4)*binomial(m,2) + 6*binomial(n,2)*binomial(m,4) for n > 2, m > 2.
T(n,m) = T(m,n).
Comments