|
%I #28 Mar 30 2024 11:36:47
%S 1,3,3,7,11,7,15,51,51,15,31,227,421,227,31,63,963,3615,3615,963,63,
%T 127,3971,30517,59747,30517,3971,127,255,16131,252231,989295,989295,
%U 252231,16131,255,511,65027,2054941,16219187,32260381,16219187,2054941,65027,511
%N Array read by antidiagonals: T(m,n) = number of dominating sets in the lattice (rook) graph K_m X K_n.
%C A set of vertices can be represented as an m X n binary matrix. If all rows contain at least one 1 then regardless of what is in each row the set will form a dominating set giving (2^n-1)^m solutions. Otherwise if only i<m rows contain at least one 1 then all columns must contain a 1 for the set to form a dominating set giving A183109(i,n) solutions.
%H Andrew Howroyd, <a href="/A287274/b287274.txt">Table of n, a(n) for n = 1..780</a>
%H Stephan Mertens, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL27/Mertens/mertens6.html">Domination Polynomial of the Rook Graph</a>, JIS 27 (2024) 24.3.7; <a href="https://arxiv.org/abs/2401.00716">arXiv:2401.00716</a> [math.CO], 2024.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DominatingSet.html">Dominating Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RookGraph.html">Rook Graph</a>
%F T(m, n) = (2^n-1)^m + Sum_{i=1..m-1} binomial(m,i) * A183109(i,n).
%e Array begins:
%e =============================================================================
%e m\n| 1 2 3 4 5 6 7
%e ---|-------------------------------------------------------------------------
%e 1 | 1 3 7 15 31 63 127...
%e 2 | 3 11 51 227 963 3971 16131...
%e 3 | 7 51 421 3615 30517 252231 2054941...
%e 4 | 15 227 3615 59747 989295 16219187 263425695...
%e 5 | 31 963 30517 989295 32260381 1048220463 33884452717...
%e 6 | 63 3971 252231 16219187 1048220463 67680006971 4358402146791...
%e 7 | 127 16131 2054941 263425695 33884452717 4358402146791 559876911043381...
%e ...
%t b[m_, n_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}];
%t a[m_, n_] := (2^n - 1)^m + Sum[ b[i, n]*Binomial[m, i], {i, 1, m - 1}];
%t Table[a[m - n + 1, n], {m, 1, 9}, {n, 1, m}] // Flatten (* _Jean-François Alcover_, Jun 12 2017, adapted from PARI *)
%o (PARI)
%o b(m,n)=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
%o a(m,n)=(2^n-1)^m + sum(i=1,m-1,b(i,n)*binomial(m,i));
%o for (i=1,7,for(j=1,7, print1(a(i,j), ",")); print);
%Y Main diagonal is A287065.
%Y Row 2 is A191341.
%Y Cf. A183109, A088699 (independent vertex sets), A290632.
%K nonn,tabl
%O 1,2
%A _Andrew Howroyd_, May 22 2017
|
