A086206 -id:A086206 - 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

A092477 Triangle read by rows: T(n,k) = (2^k - 1)^n, 1<=k<=n.

Original entry on oeis.org

1, 1, 9, 1, 27, 343, 1, 81, 2401, 50625, 1, 243, 16807, 759375, 28629151, 1, 729, 117649, 11390625, 887503681, 62523502209, 1, 2187, 823543, 170859375, 27512614111, 3938980639167, 532875860165503, 1, 6561, 5764801, 2562890625, 852891037441, 248155780267521, 67675234241018881, 17878103347812890625

Offset: 1

Reinhard Zumkeller, Mar 26 2004

T(n,1)=1; T(n,2)=A000244(n); T(n,n-1)=A086206(n); T(n,n)=A055601(n).
T(n,k) is the number of n X k binary matrices with no 0 rows. The triangular array becomes a rectangular array by lifting the restriction on k. [From Geoffrey Critzer, Dec 03 2009]
From Manfred Boergens, Jun 23 2024: (Start)
T(n,k) is the number of coverings of [n] by tuples (A_1,...,A_k) in P([n])^k, with P(.) denoting the power set.
For nonempty A_j see A218695.
For disjoint A_j see A089072.
For nonempty and disjoint A_j see A019538.
Lifting the restriction on k and swapping n,k gives A329943. (End)

			Triangle begins
 1
 1,9;
 1,27,343;
 1,81,2401,50625;
 1,243,16807,759375, 28629151 [_Geoffrey Critzer_, Dec 03 2009]

Cf. A019538, A089072, A218695, A329943.

A092477 := proc(n,k)
    (2^k-1)^n ;
end proc:
seq(seq( A092477(n,k),k=1..n),n=1..12) ; # R. J. Mathar, Nov 18 2023

Table[Table[(2^k - 1)^n, {k, 1, n}], {n, 1, 6}] // Grid (* Geoffrey Critzer, Dec 03 2009 *)

More terms from Michel Marcus, Jun 23 2024

A362013 Triangular array read by rows. T(n,k) is the number of labeled directed graphs on [n] with exactly k strongly connected components of size 1 with outdegree zero, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 27, 27, 9, 1, 2401, 1372, 294, 28, 1, 759375, 253125, 33750, 2250, 75, 1, 887503681, 171774906, 13852815, 595820, 14415, 186, 1, 3938980639167, 437664515463, 20841167403, 551353635, 8751645, 83349, 441, 1, 67675234241018881, 4263006881324024, 117484441611292, 1850148686792, 18210124870, 114709448, 451612, 1016, 1

Offset: 0

Geoffrey Critzer, Apr 03 2023

			Triangle T(n,k) begins:
       1;
       0,      1;
       1,      2,     1;
      27,     27,     9,    1;
    2401,   1372,   294,   28,  1;
  759375, 253125, 33750, 2250, 75, 1;
  ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.

Cf. A086206 (column k=0), A053763 (row sums), A361592, A350792 (a subclass of the digraphs for the case k=1 of this sequence), A003028.

nn = 6; B[n_] := n! 2^Binomial[n, 2] ; strong =Select[Import["https://oeis.org/A003030/b003030.txt", "Table"], Length@# == 2 &][[All, 2]]; s[z_] := Total[strong Table[z^i/i!, {i, 1, 58}]];
ggf[egf_] := Normal[Series[egf, {z, 0, nn}]] /.Table[z^i -> z^i/2^Binomial[i, 2], {i, 0, nn}]; Table[ Take[(Table[B[n], {n, 0, nn}] CoefficientList[   Series[ggf[Exp[(u - 1) z]]/ggf[Exp[-s[z]]], {z, 0, nn}], {z, u}])[[i]], i], {i, 1, nn + 1}]

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

A092477 Triangle read by rows: T(n,k) = (2^k - 1)^n, 1<=k<=n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions

A362013 Triangular array read by rows. T(n,k) is the number of labeled directed graphs on [n] with exactly k strongly connected components of size 1 with outdegree zero, n>=0, 0<=k<=n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica