A048291 - OEIS

%I #82 Jan 16 2024 08:11:27

%S 1,1,7,265,41503,24997921,57366997447,505874809287625,

%T 17343602252913832063,2334958727565749108488321,

%U 1243237913592275536716800402887,2630119877024657776969635243647463625,22170632855360952977731028744522744983195423

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

%C Number of relations on n labeled points such that for every point x there exists y and z such that xRy and zRx.

%C Also the number of edge covers in the complete bipartite graph K_{n,n}. - _Eric W. Weisstein_, Apr 24 2017

%C 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 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 Brendan McKay, Posting to sci.math.research, Jun 14 1999.

%H T. D. Noe, <a href="/A048291/b048291.txt">Table of n, a(n) for n = 0..32</a>

%H 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 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 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 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 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 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompleteBipartiteGraph.html">Complete Bipartite Graph</a>.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/EdgeCover.html">Edge Cover</a>.

%F a(n) = Sum_{s=0..n} binomial(n, s)*(-1)^s*2^((n-s)*n)*(1-2^(-n+s))^n.

%F From _Vladeta Jovovic_, Feb 23 2008: (Start)

%F E.g.f.: Sum_{n>=0} (2^n-1)^n*exp((1-2^n)*x)*x^n/n!.

%F a(n) = Sum_{i=0..n} Sum_{j=0..n} (-1)^(i+j)*binomial(n,i)*binomial(n,j)*2^(i*j). (End)

%F a(n) ~ 2^(n^2). - _Vaclav Kotesovec_, Jul 02 2014

%F 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 a(2) = 7:  |01|  |01|  |10|  |10|  |11|  |11|  |11|

%e            |10|  |11|  |01|  |11|  |01|  |10|  |11|.

%p seq(add((-1)^(n+k)*binomial(n, k)*(2^k-1)^n, k=0..n), n=0..15); # _Robert FERREOL_, Mar 10 2017

%t 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 (PARI) a(n)=sum(k=0,n,binomial(n,k)*(-1)^k*(2^(n-k)-1)^n)

%o (Python)

%o import math

%o f = math.factorial

%o 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 Cf. A054976, A104602, A283624, A287065, A173403.

%Y Cf. A055601, A055599, A104601, A086193 (traceless, no loops), A086206, A322661 (adj. matr. undirected edges).

%Y Diagonal of A183109.

%K nonn,easy,nice

%O 0,3

%A Joe Keane (jgk(AT)jgk.org)