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

A136516 a(n) = (2^n+1)^n.

Original entry on oeis.org

1, 3, 25, 729, 83521, 39135393, 75418890625, 594467302491009, 19031147999601100801, 2460686496619787545743873, 1280084544196357822418212890625, 2672769719437237714909813214827010049, 22366167213460480200139104627873703828439041

Offset: 0

Paul D. Hanna, Jan 02 2008

nonn

More generally, Sum_{n>=0} m^n * q^(n^2) * exp(b*q^n*x) * x^n / n! = Sum_{n>=0} (m*q^n + b)^n * x^n / n! for all q, m, b.

Main diagonal of A264871. - Omar E. Pol, Nov 27 2015

			A(x) = 1 + 3x + 5^2*x^2/2! + 9^3*x^3/3! + 17^4*x^4/4! +... + (2^n+1)^n*x^n/n! +...
A(x) = exp(x) + 2*exp(2x) + 2^4*exp(4x)*x^2/2! + 2^9*exp(8x)*x^3/3! +...+ 2^(n^2)*exp(2^n*x)*x^n/n! +...
This is a special case of the more general statement:
Sum_{n>=0} m^n * F(q^n*x)^b * log( F(q^n*x) )^n / n! = Sum_{n>=0} x^n * [y^n] F(y)^(m*q^n + b) where F(x) = exp(x), q=2, m=1, b=1.

Vincenzo Librandi, Table of n, a(n) for n = 0..45

Cf. A014050, A055601, A243918, A202989, A326011, A326012.

[(2^n+1)^n: n in [0..45]]; // Vincenzo Librandi, Apr 21 2011

seq((2^n+1)^n, n=0..30); # Robert Israel, Nov 27 2015

Table[(2^n+1)^n,{n,0,16}] (* Vladimir Joseph Stephan Orlovsky, Feb 14 2011*)

a(n)=polcoeff(sum(k=0,n,2^(k^2)*exp(2^k*x)*x^k/k!),n)

{a(n)=polcoeff(sum(k=0, n, 2^(k^2)*x^k/(1-2^k*x +x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Sep 15 2009

E.g.f.: A(x) = Sum_{n>=0} 2^(n^2) * exp(2^n*x) * x^n/n!.
O.g.f.: Sum_{n>=0} 2^(n^2)*x^n/(1 - 2^n*x)^(n+1) = Sum_{n>=0} (2^n+1)^n*x^n. [Paul D. Hanna, Sep 15 2009]
a(n) = 2^(n^2) + n 2^(n^2-n) + O(n^2 2^(n^2-2n)). - Robert Israel, Nov 27 2015

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

A060613 Number of n X n {-1,0,1} matrices with no zero rows.

Original entry on oeis.org

2, 64, 17576, 40960000, 829997587232, 148863517207035904, 238534446168822298080896, 3429499272008000182681600000000, 443223773846454955204927262062339154432

Offset: 1

Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 25 2001

nonn

Harry J. Smith, Table of n, a(n) for n = 1..45

Cf. A055601, A202989.

a(n)={(3^n - 1)^n} \\ Harry J. Smith, Jul 08 2009

{a(n, q=3, m=1, b=-1)=(m*q^n + b)^n} \\ Paul D. Hanna, Dec 26 2011

/* E.g.f. series identity: */
{a(n, q=3, m=1, b=-1)=n!*polcoeff(sum(k=0, n, m^k*q^(k^2)*exp(b*q^k*x+x*O(x^n))*x^k/k!), n)} \\ Paul D. Hanna, Dec 26 2011

/* O.g.f. series identity: */
{a(n, q=3, m=1, b=-1)=polcoeff(sum(k=0, n, m^k*q^(k^2)*x^k/(1-b*q^k*x+x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Dec 26 2011

a(n) = (3^n - 1)^n.
E.g.f.: Sum_{n>=0} 3^(n^2) * exp(-3^n*x) * x^n/n!. - Paul D. Hanna, Dec 26 2011
O.g.f.: Sum_{n>=0} 3^(n^2) * x^n/(1+3^n*x)^(n+1). - Paul D. Hanna, Dec 26 2011

More terms from Harry J. Smith, Jul 08 2009

A155202 G.f.: A(x) = exp( Sum_{n>=1} (2^n - 1)^n * x^n/n ), a power series in x with integer coefficients.

Original entry on oeis.org

1, 1, 5, 119, 12783, 5739069, 10426379903, 76135573607705, 2234839096465512877, 263966776643953756165279, 125532809982533901346598445525, 240383033223427436734891985275952307

Offset: 0

Paul D. Hanna, Feb 04 2009

nonn

More generally, for m integer, exp( Sum_{n>=1} (m^n + y)^n * x^n/n ) is a power series in x and y with integer coefficients.

			G.f.: A(x) = 1 + x + 5*x^2 + 119*x^3 + 12783*x^4 + 5739069*x^5 +...
log(A(x)) = x + 3^2*x^2/2 + 7^3*x^3/3 + 15^4*x^4/4 + 31^5*x^5/5 +...

Cf. A055601, A155200, A155202, A155810 (triangle), variants: A155205, A155209.

{a(n)=polcoeff(exp(sum(m=1,n+1,(2^m-1)^m*x^m/m)+x*O(x^n)),n)}

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

Original entry on oeis.org

1, 2, 9, 125, 6561, 1419857, 1291467969, 4902227890625, 76686282021340161, 4891005035897482905857, 1262332172765951010966606849, 1312086657801266767978668212890625

Offset: 0

Paul D. Hanna, Sep 15 2009

nonn

More generally, Sum_{n>=0} m^n * q^(n^2) * exp(b*q^n*x) * x^n/n! = Sum_{n>=0} (m*q^n + b)^n * x^n/n! for all q, m, b.

			E.g.f: A(x) = 1 + 2*x + 3^2*x^2/2! + 5^3*x^3/3! + 9^4*x^4/4! +...
A(x) = exp(x) + exp(2x)*x + 2^2*exp(4x)*x^2/2! + 2^6*exp(8x)*x^3/3! +...
This is a special case of the more general statement:
Sum_{n>=0} m^n * F(q^n*x)^b * log(F(q^n*x) )^n / n! = Sum_{n>=0} x^n * [y^n] F(y)^(m*q^n + b) where F(x) = exp(x), q=2, m=1/2, b=1.

Cf. variants: A136516, A055601, A079491.

{a(n,q=2,m=1/2,b=1)=n!*polcoeff(sum(k=0, n, m^k*q^(k^2)*exp(b*q^k*x+x*O(x^n))*x^k/k!), n)}

a(n) = (2^(n-1) + 1)^n.

A180602 a(n) = (2^(n+1) - 1)^n.

Original entry on oeis.org

1, 3, 49, 3375, 923521, 992436543, 4195872914689, 70110209207109375, 4649081944211090042881, 1227102111503512992112190463, 1291749870339606615892191271170049, 5429914198235566686555216227881787109375

Offset: 0

Paul D. Hanna, Sep 11 2010

More generally, we have the following identities:
(1) Sum_{n>=0} m^n* F(q^n*x)^b* log( F(q^n*x) )^n/n! = Sum_{n>=0} x^n* [y^n] F(y)^(m*q^n + b);
(2) Sum_{n>=0} m^n* q^(n^2)* exp(b*q^n*x)*x^n/n! = Sum_{n>=0} (m*q^n + b)^n*x^n/n! for all q, m, b.
This sequence results from (2) when q=2, m=2, b=-1.
For n >= 2, a(n) is the first number in a set of three powerful numbers in arithmetic progression with difference a(n)*(2^n - 1). - Arkadiusz Wesolowski, Aug 26 2013

			E.g.f: A(x) = 1 + 3*x + 7^2*x^2/2! + 15^3*x^3/3! + 31^4*x^4/4! +...
A(x) = exp(-x) + 2^2*exp(-2*x)*x + 2^6*exp(-4*x)*x^2/2! + 2^12*exp(-8*x)*x^3/3! +...

Cf. A086459 (signed, offset 1), variants: A055601, A079491, A136516, A165327.

Cf. A001694.

[(2^(n+1)-1)^n : n in [0..11]]; // Arkadiusz Wesolowski, Aug 26 2013

A180602:=n->(2^(n+1) - 1)^n: seq(A180602(n), n=0..10); # Wesley Ivan Hurt, Oct 09 2014

Table[(2^(n + 1) - 1)^n, {n, 0, 10}] (* Wesley Ivan Hurt, Oct 09 2014 *)

{a(n)=n!*polcoeff(sum(k=0, n, 2^(k^2+k)*exp(-2^k*x+x*O(x^n))*x^k/k!), n)}

def A180602(n): return ((1<Chai Wah Wu, Sep 13 2024

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

Name changed by Arkadiusz Wesolowski, Aug 26 2013

A086206 Number of n X n matrices with entries in {0,1} with no zero row and with zero main diagonal.

Original entry on oeis.org

0, 1, 27, 2401, 759375, 887503681, 3938980639167, 67675234241018881, 4558916353692287109375, 1213972926354344043087129601, 1284197945649659948122178573052927, 5412701932445852698371002894178179850241, 91054366938067173656011584805755385081787109375

Offset: 1

Vladeta Jovovic, Aug 27 2003

Equivalently a(n) is the number of labeled digraphs on [n] with no out-nodes. Cf. A362013. - Geoffrey Critzer, Apr 13 2023

Andrew Howroyd, Table of n, a(n) for n = 1..50

Cf. A055601, A086193, A092477, A362013.

a(n) = {(2^(n-1)-1)^n} \\ Andrew Howroyd, Jan 05 2020

a(n) = (2^(n-1)-1)^n = Sum_{k=0..n} (-1)^k*binomial(n, k)*2^((n-k)*(n-1)).
a(n) = A092477(n, n-1).
Sum_{n>=0} a(n)*x^n/A011266(n) = (Sum_{n>=0} (-x)^n/A011266(n))*(Sum_{n>=0} 2^(n(n-1))*x^n/A011266(n)). - Geoffrey Critzer, Apr 13 2023

Terms a(11) and beyond from Andrew Howroyd, Jan 05 2020

A116506 Number of singular n X n rational {0,1}-matrices with no zero rows.

Original entry on oeis.org

0, 3, 169, 28065, 16114831, 33686890209, 262530190180063, 7717643584470877185

Offset: 1

Vladeta Jovovic, Apr 03 2006

Cf. A000410, A116507, A116527, A116532.

a(n) = A055601(n) - A055165(n).

A329943 Square array read by antidiagonals: T(n,k) is the number of right total relations between set A with n elements and set B with k elements.

Original entry on oeis.org

1, 3, 1, 7, 9, 1, 15, 49, 27, 1, 31, 225, 343, 81, 1, 63, 961, 3375, 2401, 243, 1, 127, 3969, 29791, 50625, 16807, 729, 1, 255, 16129, 250047, 923521, 759375, 117649, 2187, 1, 511, 65025, 2048383, 15752961, 28629151, 11390625, 823543, 6561, 1

Offset: 1

Roy S. Freedman, Nov 24 2019

A relation R between set A with n elements and set B with k elements is a subset of the Cartesian product A x B.  A relation R is right total if for each b in B there exists an a in A such that (a,b) in R.  T(n,k) is the number of right total relations and T(k,n) is the number of left total relations: relation R is left total if for each a in A there exists a b in B such that (a,b) in R.
From Manfred Boergens, Jun 23 2024: (Start)
T(n,k) is the number of k X n binary matrices with no 0 rows.
T(n,k) is the number of coverings of [k] by tuples (A_1,...,A_n) in P([k])^n, with P(.) denoting the power set.
Swapping n,k gives A092477 (with k<=n).
For nonempty A_j see A218695 (n,k swapped).
For disjoint A_j see A089072 (n,k swapped).
For nonempty and disjoint A_j see A019538 (n,k swapped). (End)

			T(n,k) begins, for 1 <= n,k <= 9:
    1,     1,       1,         1,           1,             1,               1
    3,     9,      27,        81,         243,           729,            2187
    7,    49,     343,      2401,       16807,        117649,          823543
   15,   225,    3375,     50625,      759375,      11390625,       170859375
   31,   961,   29791,    923521,    28629151,     887503681,     27512614111
   63,  3969,  250047,  15752961,   992436543,   62523502209,   3938980639167
  127, 16129, 2048383, 260144641, 33038369407, 4195872914689, 532875860165503

Roy S. Freedman, Some New Results on Binary Relations, arXiv:1501.01914 [cs.DM], 2015.

Cf. A218695.
The diagonal T(n,n) is A055601.
A092477 = T(k,n) is the number of left total relations between A and B.
A053440 is the number of relations that are both right unique (see A329940) and right total.
A089072 is the number of functions from A to B: relations between A and B that are both right unique and left total.
A019538 is the number of surjections between A and B: relations that are right unique, right total, and left total.
A008279 is the number of injections: relations that are right unique, left total, and left unique.
A000142 is the number of bijections: relations that are right unique, left total, right total, and left unique.

Maple
```
rt:=(n,k)->(2^n-1)^k:
```

T[n_, k_] := (2^n - 1)^k; Table[T[n - k + 1, k], {n, 1, 9}, {k, 1, n}] // Flatten (* Amiram Eldar, Nov 25 2019 *)

MuPAD
```
rt:=(n,k)->(2^n-1)^k:
```

T(n,k) = (2^n - 1)^k.

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

A136516 a(n) = (2^n+1)^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

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

A060613 Number of n X n {-1,0,1} matrices with no zero rows.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

PARI

PARI

Formula

Extensions

A155202 G.f.: A(x) = exp( Sum_{n>=1} (2^n - 1)^n * x^n/n ), a power series in x with integer coefficients.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A180602 a(n) = (2^(n+1) - 1)^n.

Views

Author

Keywords

Comments

Examples

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