login
A086193
Number of n X n matrices with entries in {0,1} with no zero row, no zero column and with zero main diagonal.
8
1, 0, 1, 18, 1699, 592260, 754179301, 3562635108438, 63770601591579079, 4405870283636411477640, 1190873924687350003735546441, 1270602397076493907445608866890778, 5381240610642043789096251476993474339179
OFFSET
0,4
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
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
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
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 *)
PROG
(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
CROSSREFS
Cf. A048291.
Sequence in context: A003030 A276016 A086366 * A064347 A253121 A067303
KEYWORD
nonn
AUTHOR
W. Edwin Clark, Aug 25 2003
EXTENSIONS
More terms from Brendan McKay, Aug 27 2003
a(0)=1 prepended by Andrew Howroyd, Sep 09 2018
STATUS
approved