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

1, 1, 7, 265, 41503, 24997921, 57366997447, 505874809287625, 17343602252913832063, 2334958727565749108488321, 1243237913592275536716800402887, 2630119877024657776969635243647463625, 22170632855360952977731028744522744983195423

Offset: 0

Author

Joe Keane (jgk(AT)jgk.org)

Keywords

• nonn
• easy
• nice

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

Examples

			a(2) = 7:  |01|  |01|  |10|  |10|  |11|  |11|  |11|
           |10|  |11|  |01|  |11|  |01|  |10|  |11|.
		

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, and R. Maurice, Combinatorial Hopf algebra structure on packed square matrices, arXiv preprint arXiv:1306.6605 [math.CO], 2013.
• David Dolžan and 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).
• Steven Schlicker, Roman Vasquez, and Rachel Wofford, Integer Sequences from Configurations in the Hausdorff Metric Geometry via Edge Covers of Bipartite Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.6.6.
• Stefan Schwarz, The semigroup of fully indecomposable relations and Hall relations, Czechoslovak Mathematical Journal, 23 (1973), 151-163.
• 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.

Crossrefs

Cf. A054976, A104602, A283624, A287065, A173403.

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

Diagonal of A183109.

Programs

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 *)

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

Formula

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

From Vladeta Jovovic, Feb 23 2008: (Start)

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)

a(n) ~ 2^(n^2). - Vaclav Kotesovec, Jul 02 2014

a(n) = Sum_{s=0..n-1} binomial(n,s)*(-1)^s*A092477(n,n-s), n > 0. - R. J. Mathar, Nov 18 2023