|
|
A048291
|
|
Number of {0,1} n X n matrices with no zero rows or columns.
|
|
70
|
|
|
1, 1, 7, 265, 41503, 24997921, 57366997447, 505874809287625, 17343602252913832063, 2334958727565749108488321, 1243237913592275536716800402887, 2630119877024657776969635243647463625, 22170632855360952977731028744522744983195423
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Number of relations on n labeled points such that for every point x there exists y and z such that xRy and zRx.
Also the number of edge covers in the complete bipartite graph K_{n,n}. - Eric W. Weisstein, Apr 24 2017
Counts labeled digraphs (loops allowed, no multiarcs) on n nodes where each indegree and each outdegree is >= 1. The corresponding sequence for unlabeled digraphs (1, 5, 55, 1918,... for n >= 1) seems not to be in the OEIS. - R. J. Mathar, Nov 21 2023
These relations form a subsemigroup of the semigroup of all binary relations on [n]. The zero element is the universal relation (all 1's matrix). See Schwarz link. - Geoffrey Critzer, Jan 15 2024
|
|
REFERENCES
|
Brendan McKay, Posting to sci.math.research, Jun 14 1999.
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Edge Cover.
|
|
FORMULA
|
a(n) = Sum_{s=0..n} binomial(n, s)*(-1)^s*2^((n-s)*n)*(1-2^(-n+s))^n.
E.g.f.: Sum_{n>=0} (2^n-1)^n*exp((1-2^n)*x)*x^n/n!.
a(n) = Sum_{i=0..n} Sum_{j=0..n} (-1)^(i+j)*binomial(n,i)*binomial(n,j)*2^(i*j). (End)
|
|
EXAMPLE
|
a(2) = 7: |01| |01| |10| |10| |11| |11| |11|
|10| |11| |01| |11| |01| |10| |11|.
|
|
MAPLE
|
seq(add((-1)^(n+k)*binomial(n, k)*(2^k-1)^n, k=0..n), n=0..15); # Robert FERREOL, Mar 10 2017
|
|
MATHEMATICA
|
Flatten[{1, Table[Sum[Binomial[n, k]*(-1)^k*(2^(n-k)-1)^n, {k, 0, n}], {n, 1, 15}]}] (* Vaclav Kotesovec, Jul 02 2014 *)
|
|
PROG
|
(PARI) a(n)=sum(k=0, n, binomial(n, k)*(-1)^k*(2^(n-k)-1)^n)
(Python)
import math
f = math.factorial
def A048291(n): return sum([(f(n)/f(s)/f(n - s))*(-1)**s*(2**(n - s) - 1)**n for s in range(0, n+1)]) # Indranil Ghosh, Mar 14 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
Joe Keane (jgk(AT)jgk.org)
|
|
STATUS
|
approved
|
|
|
|