A086193 -id:A086193 - cp's OEIS frontend

A006129 a(0), a(1), a(2), ... satisfy Sum_{k=0..n} a(k)*binomial(n,k) = 2^binomial(n,2), for n >= 0.

1, 0, 1, 4, 41, 768, 27449, 1887284, 252522481, 66376424160, 34509011894545, 35645504882731588, 73356937912127722841, 301275024444053951967648, 2471655539737552842139838345, 40527712706903544101000417059892, 1328579255614092968399503598175745633

Offset: 0

Colin Mallows

Also labeled graphs on n unisolated nodes (inverse binomial transform of A006125). - Vladeta Jovovic, Apr 09 2000

Also the number of edge covers of the complete graph K_n. - Eric W. Weisstein, Mar 30 2017

			2^binomial(n,2) = 1 + binomial(n,2) + 4*binomial(n,3) + 41*binomial(n,4) + 768*binomial(n,5) + ...

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 0..50
A. N. Bhavale, B. N. Waphare, Basic retracts and counting of lattices, Australasian J. of Combinatorics (2020) Vol. 78, No. 1, 73-99.
C. L. Mallows & N. J. A. Sloane, Emails, May 1991
N. J. A. Sloane, Transforms
R. Tauraso, Edge cover time for regular graphs, JIS 11 (2008) 08.4.4.
Eric Weisstein's World of Mathematics, Complete Graph
Eric Weisstein's World of Mathematics, Edge Cover

Row sums of A054548.

Cf. A322661 (if loops allowed), A086193 (directed edges), A002494 (unlabeled).

a:= proc(n) option remember; `if`(n=0, 1,
      2^binomial(n, 2) - add(a(k)*binomial(n,k), k=0..n-1))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Oct 26 2012

a = Sum[2^Binomial[n, 2] x^n/n!, {n, 0, 20}]; Range[0, 20]! CoefficientList[Series[a/Exp[x], {x, 0, 20}], x] (* Geoffrey Critzer, Oct 21 2011 *)
Table[Sum[(-1)^(n - k) Binomial[n, k] 2^Binomial[k, 2], {k, 0, n}], {n, 0, 20}] (* Vaclav Kotesovec, May 04 2015 *)

for(n=0,25, print1(sum(k=0,n,(-1)^(n-k)*binomial(n, k)*2^binomial(k, 2)), ", ")) \\ G. C. Greubel, Mar 30 2017

from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def a(n): return 1 if n==0 else 2**binomial(n, 2) - sum(a(k)*binomial(n, k) for k in range(n))
print([a(n) for n in range(21)]) # Indranil Ghosh, Aug 12 2017

a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n, k)*2^binomial(k, 2).
E.g.f.: A(x)/exp(x) where A(x) = Sum_{n>=0} 2^C(n,2) x^n/n!. - Geoffrey Critzer, Oct 21 2011
a(n) ~ 2^(n*(n-1)/2). - Vaclav Kotesovec, May 04 2015

More terms from Vladeta Jovovic, Apr 09 2000

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

Original entry on oeis.org

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

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

A086366 Number of labeled n-node digraphs in which every node belongs to a directed cycle.

Original entry on oeis.org

1, 0, 1, 18, 1699, 587940, 750744901, 3556390155318, 63740128872703879, 4405426607409460017480, 1190852520892329350092354441, 1270598627613805616203391468226138, 5381238039128882594932248239301142751179, 90766634183072089515270648224715368261615375340

Offset: 0

Valery A. Liskovets and Vladeta Jovovic, Sep 04 2003

nonn

These are the directed graphs whose strong components exclude a single vertex. - Andrew Howroyd, Jan 15 2022

Andrew Howroyd, Table of n, a(n) for n = 0..50
Valery Liskovets, Labeled digraphs in which every node belongs to a directed cycle [Broken link]

Column k=0 of A361592.
The unlabeled version is A361586.
Cf. A003030, A086193.

G(p)={my(n=serprec(p,x)); serconvol(p, sum(k=0, n-1, x^k/2^(k*(k-1)/2), O(x^n)))}
U(p)={my(n=serprec(p,x)); serconvol(p, sum(k=0, n-1, x^k*2^(k*(k-1)/2), O(x^n)))}
DigraphEgf(n)={sum(k=0, n, 2^(k*(k-1))*x^k/k!, O(x*x^n) )}
seq(n)={Vec(serlaplace(U(1/G(exp(x+log(U(1/G(DigraphEgf(n)))))))))} \\ Andrew Howroyd, Jan 15 2022

a(0)=1 prepended and terms a(12) and beyond from Andrew Howroyd, Jan 15 2022

A121933 Number of labeled digraphs with n arcs for which every vertex has indegree at least one and outdegree at least one.

Original entry on oeis.org

1, 0, 1, 2, 18, 158, 1788, 23930, 370886, 6527064, 128542420, 2800362536, 66858556196, 1735834171276, 48689118113374, 1467253017578672, 47275138863637080, 1621757692715997136, 59013695834307968254, 2270400832166224741596, 92078072790064946096284

Offset: 0

Vladeta Jovovic, Sep 02 2006

Nathaniel Johnston, Table of n, a(n) for n = 0..60

Cf. A121252, A086193 (by # of nodes), A367500 (unlabeled version).

n:=20: t:=taylor(sum(sum((-1)^(m-k)*binomial(m,k)*((1+x)^(k-1)-1)^k*((1+x)^k-1)^(m-k),k=0..m),m=0..n),x,n+1): seq(coeff(t,x,m),m=0..n); # Nathaniel Johnston, Apr 28 2011

Flatten[{1,Rest[CoefficientList[Series[Sum[Sum[(-1)^(n-k)*Binomial[n,k]*((1+x)^(k-1)-1)^k*((1+x)^k-1)^(n-k),{k,0,n}],{n,1,20}],{x,0,20}],x]]}] (* Vaclav Kotesovec, May 07 2014 *)

G.f.: Sum(Sum((-1)^(n-k)*binomial(n,k)*((1+x)^(k-1)-1)^k*((1+x)^k-1)^(n-k),k=0..n),n=0..infinity).
a(n) ~ c * n! / (sqrt(n) * (log(2))^(2*n)), where c = 0.0722246614111436... . - Vaclav Kotesovec, May 07 2014
In closed form, c = 1/(sqrt(Pi*(1-log(2))) * log(2) * 2^(4+log(2)/2)). - Vaclav Kotesovec, May 04 2015

A367500 The number of digraphs on n unlabeled nodes with each indegree >=1 and each outdegree >=1.

Original entry on oeis.org

1, 0, 1, 5, 90, 5332, 1076904, 713634480, 1586714659885, 12154215627095823, 328282817968663707661, 31834558934274542784372501, 11234635799120735533158176241587, 14576389568173850099660541344975456791, 70075904848498231395100110985113641934719377

Offset: 0

R. J. Mathar, Nov 20 2023

nonn

Digraphs counted here must be loopless, but not necessarily connected.
The definition is not strictly saying that there is no (global) source or sink, because the graphs are counted without considering (strong or weak) connectivity.
(The weakly connected digraphs of this type start 1,0,1,5,89,5327,...)

			From _Andrew Howroyd_, Jan 02 2024: (Start)
Example of a digraph counted by this sequence but not by A361586:
   o <---> o ----> o ----> o <---> o
In the above example, the 3rd vertex has both an in arc and an out arc, but is not part of any directed cycle. (End)

Andrew Howroyd, Table of n, a(n) for n = 0..50
R. J. Mathar, Illustrations (2023), 335 pages

Cf. A121933 (labeled version), A086193 (labeled digraphs), A002494 (undirected graphs), A361586 (all vertices in at least one directed cycle).

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
K(q, t)={sum(j=1, #q, gcd(t, q[j]))}
a(n) = {if(n==0, 1, sum(k=1, n, my(s=0, m=n-k); forpart(p=k, s += permcount(p) * prod(i=1, #p, 2^(K(p,p[i])-1)-1) * polcoef(exp(sum(t=1, m, (1-2^K(p, t))/t*x^t) + O(x*x^m)), m)); s/k!))} \\ Andrew Howroyd, Jan 02 2024

Terms a(6) and beyond from Andrew Howroyd, Jan 02 2024

A361210 Number of labeled digraphs on [n] with exactly 1 in-node and exactly 1 out-node.

Original entry on oeis.org

0, 1, 2, 15, 588, 83295, 40993230, 70413420511, 433343743592312, 9825711749274316671, 840137012096473747415610, 275596225117501271622460109871, 351011149451321734143551287903432452, 1749719217881846572487198585072701742763487, 34317835907818751756576624929762210160396817182918

Offset: 0

Geoffrey Critzer, Apr 09 2023

nonn

Here, an in-node is a node whose outdegree is zero. An out-node is a node whose in-degree is zero. The in-node is not necessarily distinct from the out-node.

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.

Cf. A086193 (no out-nodes nor in-nodes).

nn = 14; B[n_] := n! 2^Binomial[n, 2] ; e[z_] := Sum[z^n/B[n], {n, 0, nn}];
g[z_] := Sum[2^(n (n - 1)) z^n/B[n], {n, 0, nn}];egf[ggf_] := Normal[Series[ggf, {z, 0, nn}]] /. Table[z^i -> z^i*2^Binomial[i, 2], {i, 0, nn}];Table[n!, {n, 0, nn}] Map[Coefficient[#, u v] &, CoefficientList[Series[Exp[(u - 1) ( v - 1) z] egf[e[(u - 1) z] g[z] e[(v - 1) z]], {z, 0, nn}], z]]

cp's OEIS Frontend

A006129 a(0), a(1), a(2), ... satisfy Sum_{k=0..n} a(k)*binomial(n,k) = 2^binomial(n,2), for n >= 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A086366 Number of labeled n-node digraphs in which every node belongs to a directed cycle.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A121933 Number of labeled digraphs with n arcs for which every vertex has indegree at least one and outdegree at least one.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A367500 The number of digraphs on n unlabeled nodes with each indegree >=1 and each outdegree >=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A361210 Number of labeled digraphs on [n] with exactly 1 in-node and exactly 1 out-node.

Views

Author

Keywords

Comments

Links