A283624 -id:A283624 - cp's OEIS frontend

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

Joe Keane (jgk(AT)jgk.org)

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

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

Brendan McKay, Posting to sci.math.research, Jun 14 1999.

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.

Cf. A054976, A104602, A283624, A287065, A173403.
Cf. A055601, A055599, A104601, A086193 (traceless, no loops), A086206, A322661 (adj. matr. undirected edges).
Diagonal of A183109.

seq(add((-1)^(n+k)*binomial(n, k)*(2^k-1)^n, k=0..n), n=0..15); # Robert FERREOL, Mar 10 2017

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

a(n)=sum(k=0,n,binomial(n,k)*(-1)^k*(2^(n-k)-1)^n)

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

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

A283654 Triangle T(n,m) read by rows: number of n X m binary matrices with no rows or columns in which all entries are the same (n >= 1, 1 <= m <= n).

Original entry on oeis.org

0, 0, 2, 0, 6, 102, 0, 14, 906, 22874, 0, 30, 6510, 417810, 17633670, 0, 62, 42666, 6644714, 622433730, 46959933962, 0, 126, 267582, 99044946, 20218802310, 3204360965106, 451575174961302, 0, 254, 1641786, 1430529674, 630917888610, 208308918928634, 60134626974122946, 16271255119687320314

Offset: 1

Robert FERREOL, Mar 14 2017

			The T(2,3)=6 matrices are
1 0 1
0 1 0
and the matrices obtained by permutations of rows and columns.
First values in triangle
0;
0, 2;
0, 6, 102;
0, 14, 906, 22874;
0, 30, 6510, 417810, 17633670;
0, 62, 42666, 6644714, 622433730, 46959933962;
0, 126, 267582, 99044946, 20218802310, 3204360965106, 451575174961302;

Diagonal gives A283624.

Cf. A183109.

T0:=(n,m)->add((-1)^(m+k)*binomial(n,k)*(2^k-1)^m, k=0..n):
T:=(n,m)->2*T0(n,m)+2^(n*m)+(2^n-2)^m+(2^m-2)^n-2*(2^m-1)^n-2*(2^n-1)^m:
seq(seq(T(n,m), m=1..n),n=1..10);

T[n_, m_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}]; Flatten[Table[2*T[n, m] + 2^(n*m) + (2^n - 2)^m + (2^m - 2)^n - 2*(2^m - 1)^n - 2*(2^n - 1)^m, {n, 10}, {m, n}]] (* Indranil Ghosh, Mar 14 2017 *)

T(n, m) = sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
tabl(nn) = {for(n=1, nn, for(m=1, n, print1(2*T(n,m) + 2^(n*m) + (2^n - 2)^m + (2^m - 2)^n - 2*(2^m - 1)^n - 2*(2^n - 1)^m,", ");); print(););};
tabl(10); \\ Indranil Ghosh, Mar 14 2017

import math
f=math.factorial
def C(n,r): return f(n)//f(r)//f(n - r)
def T(n,m): return sum([(-1)**j*C(m,j)*(2**(m - j) - 1)**n for j in range (0, m+1)])
i=1
for n in range(1,11):
    for m in range(1, n+1):
        print(str(i)+" "+str(2*T(n, m) + 2**(n*m) + (2**n - 2)**m + (2**m - 2)**n - 2*(2**m - 1)**n - 2*(2**n - 1)**m))
        i+=1 # Indranil Ghosh, Mar 14 2017

T(n,m) = T(m,n) = 2*A183109(n,m) + 2^(n*m) + (2^n-2)^m + (2^m-2)^n - 2*(2^m-1)^n - 2*(2^n-1)^m.

T(n,1)=0, T(n,2)=2^n-2, T(n,3)=6^n-6*(3^n-2^n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula