A086193 Number of n X n matrices with entries in {0,1} with no zero row, no zero column and with zero main diagonal.

1, 0, 1, 18, 1699, 592260, 754179301, 3562635108438, 63770601591579079, 4405870283636411477640, 1190873924687350003735546441, 1270602397076493907445608866890778, 5381240610642043789096251476993474339179

Offset: 0

Author

W. Edwin Clark, Aug 25 2003

Keywords

• nonn

Comments

Also the number of simple labeled digraphs on n nodes for which every vertex has indegree at least one and outdegree at least one.

Also the number of edge covers on the n-crown graph. - Eric W. Weisstein, May 19 2017

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..50
• R. W. Robinson. Counting digraphs with restrictions on the strong components, (1996). W(n).
• R. W. Robinson, Counting digraphs with restrictions on the strong components, 1996 [Local copy, with permission]
• Martin Svatoš, Peter Jung, Jan Tóth, Yuyi Wang, and Ondřej Kuželka, On Discovering Interesting Combinatorial Integer Sequences, arXiv:2302.04606 [cs.LO], 2023, p. 17.
• Eric Weisstein's World of Mathematics, Crown Graph
• Eric Weisstein's World of Mathematics, Edge Cover

Crossrefs

Cf. A048291.

Programs

Mathematica

Table[ it = (Partition[ #1, n ] &) /@ IntegerDigits[ Range[ 0, -1 + 2^n^2 ], 2, n^2 ]; Count[ it, (q_)?MatrixQ /; Tr[ q ] === 0 && (Times @@ (Plus @@@ q)) > 0 && (Times @@ (Plus @@@ Transpose[ q ]) > 0) ], {n, 1, 4} ] (* Wouter Meeussen, Aug 25 2003 *)
Table[Sum[(-1)^(n-r)*Binomial[n, r]*(2^(r-1)-1)^r*(2^r-1)^(n-r), {r,0,n}],{n,1,15}] (* Vaclav Kotesovec, May 04 2015 after Vladeta Jovovic *)

PARI

a(n)={sum(r=0, n, (-1)^(n-r)*binomial(n, r)*(2^(r-1)-1)^r*(2^r-1)^(n-r))} \\ Andrew Howroyd, Sep 09 2018

Formula

a(n) = Sum_{r=0..n} (-1)^(n-r)*binomial(n, r)*(2^(r-1)-1)^r*(2^r-1)^(n-r). - Vladeta Jovovic, Aug 27 2003

a(n) = sum( f(n, r), r=0..n ) where f(n, r) = binomial(n, r) (-1)^r (1-2^(-n+r+1))^(n-r) (1-2^(-n+r))^r 2^((n-r)(n-1)). - Brendan McKay, Aug 27 2003

E.g.f.: Sum_{k>=0} (2^(n-1)-1)^n*exp((1-2^n)*x)*x^n/n!. - Vladeta Jovovic, Feb 23 2008

a(n) ~ 2^(n*(n-1)). - Vaclav Kotesovec, May 04 2015

Extensions

More terms from Brendan McKay, Aug 27 2003

a(0)=1 prepended by Andrew Howroyd, Sep 09 2018