A287065 Number of dominating sets on the n X n rook graph.

1, 11, 421, 59747, 32260381, 67680006971, 559876911043381, 18412604442711949187, 2416403019417984915336061, 1267413006543912045144741284411, 2658304092145691708492995820522716981, 22300364428188338185156192161829091442585827

Offset: 1

Author

Eric W. Weisstein, May 19 2017

Keywords

• nonn

Comments

Number of {0,1} n X n matrices with no zero rows or no zero columns. - Geoffrey Critzer, Jan 15 2024

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..50
• Eric Weisstein's World of Mathematics, Dominating Set
• Eric Weisstein's World of Mathematics, Rook Graph

Crossrefs

Main diagonal of A287274.

Row sums of A368831.

Cf. A183109, A002720, A048291, A173403.

Programs

Mathematica

Table[(2^n - 1)^n + Sum[Binomial[n, i] Sum[(-1)^j (-1 + 2^(n - j))^i Binomial[n, j], {j, 0, n}], {i, n - 1}], {n, 20}] (* Eric W. Weisstein, May 27 2017 *)

PARI

b(m,n)=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
a(n)=(2^n-1)^n + sum(i=1,n-1,b(n,i)*binomial(n,i)); \\ Andrew Howroyd, May 22 2017

Formula

a(n) = (2^n-1)^n + Sum_{i=1..n-1} binomial(n,i) * A183109(n,i). - Andrew Howroyd, May 22 2017

Extensions

a(6)-a(12) from Andrew Howroyd, May 22 2017