|
|
A048291
|
|
Number of {0,1} n X n matrices with no zero rows or columns.
|
|
51
|
|
|
1, 1, 7, 265, 41503, 24997921, 57366997447, 505874809287625, 17343602252913832063, 2334958727565749108488321, 1243237913592275536716800402887, 2630119877024657776969635243647463625
(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
|
|
REFERENCES
|
Brendan McKay, Posting to sci.math.research, Jun 14 1999.
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..32
H. Cheballah, S. Giraudo, R. Maurice, Combinatorial Hopf algebra structure on packed square matrices, arXiv preprint arXiv:1306.6605 [math.CO], 2013.
David Dolžan, Gabriel Verret, The automorphism group of the zero-divisor digraph of matrices over an antiring, arXiv:1908.04614 [math.AC], 2019.
R. J. Mathar, The number of nXm matrices with at most k 1's in each row or column, (2014).
R. Tauraso, Edge cover time for regular graphs, JIS 11 (2008) 08.4.4
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
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((2^n-1)^n*exp((1-2^n)*x)*x^n/n!,n=0..infinity). a(n) = Sum(Sum((-1)^(i+j)*binomial(n,i)*binomial(n,j)*2^(i*j),j = 0 .. n),i = 0 .. n). - Vladeta Jovovic, Feb 23 2008
a(n) ~ 2^(n^2). - Vaclav Kotesovec, Jul 02 2014
|
|
MAPLE
|
seq(sum((-1)^(n+k)*binomial(n, k)*(2^k-1)^n, k=1..n), n=1..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
|
Cf. A054976, A104602, A283624.
Cf. A055601, A055599, A104601, A086193, A086206.
Diagonal of A183109.
Sequence in context: A324095 A290880 A231486 * A015089 A179565 A069449
Adjacent sequences: A048288 A048289 A048290 * A048292 A048293 A048294
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
Joe Keane (jgk(AT)jgk.org)
|
|
STATUS
|
approved
|
|
|
|