cp's OEIS Frontend

A048291 Number of {0,1} n X n matrices with no zero rows or columns.

%I A048291 #83 Feb 16 2025 08:32:39
%S A048291 1,1,7,265,41503,24997921,57366997447,505874809287625,
%T A048291 17343602252913832063,2334958727565749108488321,
%U A048291 1243237913592275536716800402887,2630119877024657776969635243647463625,22170632855360952977731028744522744983195423
%N A048291 Number of {0,1} n X n matrices with no zero rows or columns.
%C A048291 Number of relations on n labeled points such that for every point x there exists y and z such that xRy and zRx.
%C A048291 Also the number of edge covers in the complete bipartite graph K_{n,n}. - _Eric W. Weisstein_, Apr 24 2017
%C A048291 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
%C A048291 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
%D A048291 Brendan McKay, Posting to sci.math.research, Jun 14 1999.
%H A048291 T. D. Noe, <a href="/A048291/b048291.txt">Table of n, a(n) for n = 0..32</a>
%H A048291 H. Cheballah, S. Giraudo, and R. Maurice, <a href="http://arxiv.org/abs/1306.6605">Combinatorial Hopf algebra structure on packed square matrices</a>, arXiv preprint arXiv:1306.6605 [math.CO], 2013.
%H A048291 David Dolžan and Gabriel Verret, <a href="https://arxiv.org/abs/1908.04614">The automorphism group of the zero-divisor digraph of matrices over an antiring</a>, arXiv:1908.04614 [math.AC], 2019.
%H A048291 R. J. Mathar, <a href="/A247158/a247158.pdf">The number of nXm matrices with at most k 1's in each row or column</a>, (2014).
%H A048291 Steven Schlicker, Roman Vasquez, and Rachel Wofford, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Wofford/wofford4.html">Integer Sequences from Configurations in the Hausdorff Metric Geometry via Edge Covers of Bipartite Graphs</a>, J. Int. Seq. (2023) Vol. 26, Art. 23.6.6.
%H A048291 Stefan Schwarz, <a href="https://dml.cz/handle/10338.dmlcz/101153">The semigroup of fully indecomposable relations and Hall relations</a>, Czechoslovak Mathematical Journal, 23 (1973), 151-163.
%H A048291 R. Tauraso, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Tauraso/tauraso18.html">Edge cover time for regular graphs</a>, JIS 11 (2008) 08.4.4.
%H A048291 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CompleteBipartiteGraph.html">Complete Bipartite Graph</a>.
%H A048291 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/EdgeCover.html">Edge Cover</a>.
%F A048291 a(n) = Sum_{s=0..n} binomial(n, s)*(-1)^s*2^((n-s)*n)*(1-2^(-n+s))^n.
%F A048291 From _Vladeta Jovovic_, Feb 23 2008: (Start)
%F A048291 E.g.f.: Sum_{n>=0} (2^n-1)^n*exp((1-2^n)*x)*x^n/n!.
%F A048291 a(n) = Sum_{i=0..n} Sum_{j=0..n} (-1)^(i+j)*binomial(n,i)*binomial(n,j)*2^(i*j). (End)
%F A048291 a(n) ~ 2^(n^2). - _Vaclav Kotesovec_, Jul 02 2014
%F A048291 a(n) = Sum_{s=0..n-1} binomial(n,s)*(-1)^s*A092477(n,n-s), n > 0. - _R. J. Mathar_, Nov 18 2023
%e A048291 a(2) = 7:  |01|  |01|  |10|  |10|  |11|  |11|  |11|
%e A048291            |10|  |11|  |01|  |11|  |01|  |10|  |11|.
%p A048291 seq(add((-1)^(n+k)*binomial(n, k)*(2^k-1)^n, k=0..n), n=0..15); # _Robert FERREOL_, Mar 10 2017
%t A048291 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 *)
%o A048291 (PARI) a(n)=sum(k=0,n,binomial(n,k)*(-1)^k*(2^(n-k)-1)^n)
%o A048291 (Python)
%o A048291 import math
%o A048291 f = math.factorial
%o A048291 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
%Y A048291 Cf. A054976, A104602, A283624, A287065, A173403.
%Y A048291 Cf. A055601, A055599, A104601, A086193 (traceless, no loops), A086206, A322661 (adj. matr. undirected edges).
%Y A048291 Diagonal of A183109.
%K A048291 nonn,easy,nice
%O A048291 0,3
%A A048291 Joe Keane (jgk(AT)jgk.org)