A003030 -id:A003030 - cp's OEIS frontend

A035512 Number of unlabeled strongly connected digraphs with n nodes.

1, 1, 1, 5, 83, 5048, 1047008, 705422362, 1580348371788, 12139024825260556, 328160951349343885604, 31831080872412589394328804, 11234274997368899732057135454531, 14576252633139820879894296847900227082

Offset: 0

Ronald C. Read

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 218.
V. A. Liskovets, A contribution to the enumeration of strongly connected digraphs, Dokl. AN BSSR, 17 (1973), 1077-1080, MR49#4849.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..18 from R. W. Robinson)
A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 251. Book's website
Eric Weisstein's World of Mathematics, Strongly Connected Digraph.

The labeled version is A003030.
Row sums of A057276.
Column sums of A350753.
Cf. A003085, A049387, A350489, A350752.

\\ See PARI link in A350489 for program code.
A035512seq(15) \\ Andrew Howroyd, Jan 13 2022

a(12) and a(13) added by N. J. A. Sloane from the Robinson report, Oct 17 2006

A003027 Number of weakly connected digraphs with n labeled nodes.

Original entry on oeis.org

1, 3, 54, 3834, 1027080, 1067308488, 4390480193904, 72022346388181584, 4721717643249254751360, 1237892809110149882059440768, 1298060596773261804821355107253504, 5444502293680983802677246555274553481984, 91343781554246596956424128384394531707099632640

Offset: 1

N. J. A. Sloane

R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..30
A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.

The unlabeled case is A003085.
Row sums of A062735.
Cf. A053763 (not necessarily connected), A003030 (strongly connected).

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

Range[0, 20]! CoefficientList[Series[D[1 + Log[Sum[2^(n^2 - n) x^n/n!, {n, 0, 20}]], x], {x, 0,20}], x]
c[n_]:=2^(n(n-1))-Sum[k Binomial[n,k]c[k] 2^((n-k)(n-k-1)),{k,1,n-1}]/n;c[0]=1;Table[c[i],{i,0,20}]  (* Geoffrey Critzer, Oct 24 2012 *)

v=Vec(log(sum(n=0, default(seriesprecision), 2^(n^2-n)*x^n/n!))); for(i=1, #v, v[i]*=(i-1)!); v \\ Charles R Greathouse IV, Feb 14 2011

b = lambda n: 2^(n^2-n)
@cached_function
def A003027(n):
    return b(n) - sum(k*binomial(n, k)*b(n-k)*A003027(k) for k in (1..n-1)) / n
[A003027(n) for n in (1..13)] # Peter Luschny, Jan 18 2016

a(n) = A062738(n)/2^n, since binary relations = digraphs with loops. - Ralf Stephan and Vladeta Jovovic, Mar 24 2004
E.g.f.: log(sum n>=0, 2^(n^2-n)*x^n/n!).
a(n) = A053763(n) - (1/n) * Sum_{k=1..n-1} k*C(n,k)*a(k)*A053763(n-k). - Geoffrey Critzer, Oct 24 2012

Corrected and extended by Vladeta Jovovic, Goran Kilibarda

A057273 Triangle T(n,k) of the number of strongly connected digraphs on n labeled nodes and with k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 2, 9, 6, 1, 0, 0, 0, 0, 6, 84, 316, 492, 417, 212, 66, 12, 1, 0, 0, 0, 0, 0, 24, 720, 6440, 26875, 65280, 105566, 122580, 106825, 71700, 37540, 15344, 4835, 1140, 190, 20, 1, 0, 0, 0, 0, 0, 0, 120, 6480, 107850, 868830, 4188696, 13715940

Offset: 1

Vladeta Jovovic, Goran Kilibarda, Sep 14 2000

			Triangle begins:
  [1] 1;
  [2] 0,0,1;
  [3] 0,0,0,2,9,6,1;
  [4] 0,0,0,0,6,84,316,492,417,212,66,12,1;
  ...
Number of strongly connected digraphs on 3 labeled nodes is 18 = 2+9+6+1.

Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041. See Table 2.

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)
Kassie Archer, Ira M. Gessel, Christina Graves, and Xuming Liang, Counting acyclic and strong digraphs by descents, arXiv:1909.01550 [math.CO], 20 Mar 2020. See Table 2.

Row sums give A003030.
The unlabeled version is A057276.
Cf. A057271, A057272, A057274, A057275, A062735.
Cf. A123554, A339590, A339807.

B(nn, e=2)={my(v=vector(nn)); for(n=1, nn, v[n] = e^(n*(n-1)) - sum(k=1, n-1, binomial(n,k)*e^((n-1)*(n-k))*v[k])); v}
Strong(n, e=2)={my(u=B(n, e), v=vector(n)); v[1]=1; for(n=2, #v, v[n] = u[n] + sum(j=1, n-1, binomial(n-1, j-1)*u[n-j]*v[j])); v}
row(n)={ Vecrev(Strong(n, 1+'y)[n]) }
{ for(n=1, 5, print(row(n))) } \\ Andrew Howroyd, Jan 10 2022

Terms a(46) and beyond from Andrew Howroyd, Jan 10 2022

A070322 Number of primitive n X n real (0,1)-matrices.

Original entry on oeis.org

1, 1, 3, 139, 25575, 18077431, 47024942643

Offset: 0

N. J. A. Sloane, Aug 22 2003

An n X n nonnegative matrix A is primitive iff every element of A^k is > 0 for some power k. If A is primitive then the power which should have all positive entries is <= n^2 - 2n + 2 (Wielandt).

Equivalently, a(n) is the number of n X n Boolean relation matrices that converge in their powers to U, the all 1's matrix. From the Rosenblatt reference we know that the relations that converge to U are precisely those that are strongly connected and whose cycle lengths have gcd equal to 1. In particular, if a strongly connected relation has at least one self loop then it converges to U. So A003030(n)*(2^n - 1) < a(n) < A003030(n)*2^n. Almost all (0,1)-matrices are primitive. - Geoffrey Critzer, Jul 20 2022

Sachkov, V. N. and Tarakanov, V. E., Combinatorics of Nonnegative Matrices. Translations of Mathematical Monographs, 213. American Mathematical Society, Providence, RI, 2002.

Nicholas R. Beaton, Walks obeying two-step rules on the square lattice: full, half and quarter planes, arXiv:2010.06955 [math.CO], 2020.
S. J. Leon, Linear Algebra with Applications: the Perron-Frobenius Theorem [Cached copy at the Wayback Machine]
G. Markowsky, Bounds on the index and period of a binary relation on a finite set, Semigroup Forum, Vol 13 (1977), 253-259.
D. Rosenblatt, On the graphs of finite Boolean relation matrices, Journal of Research of the National Bureau of Standards, 67B No. 4, 1963.
Helmut Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z. 52 (1950), 642-648.
Index entries for sequences related to binary matrices

Cf. A003030.

Table[ it=Partition[ #, n ]&/@IntegerDigits[ Range[ 0, -1+2^n^2 ], 2, n^2 ]; Count [ it, (q_?MatrixQ) /; (Max@@Table[ Min@@Flatten[ MatrixPower[ q, k ] ], {k, 1, n^2-2n+2} ] )>0 ], {n, 1, 4} ]

For asymptotics see Sachkov and Tarakanov.

Wouter Meeussen computed a(0) through a(4), Aug 22 2003
I. J. Kennedy computed a(0) through a(5), Aug 22 2003
a(6) from Pontus von Brömssen, Aug 09 2022

A003028 Number of digraphs on n labeled nodes with a source.

Original entry on oeis.org

1, 3, 51, 3614, 991930, 1051469032, 4366988803688, 71895397383029040, 4719082081411731363408, 1237678715644664931691596416, 1297992266840866792981316221144960, 5444416466164313011147841248189209354496, 91343356480627224177654291875698256656613808896

Offset: 1

N. J. A. Sloane

Here a source is a node that is connected by a directed path to every other node in the digraph (but does not necessarily have indegree zero). - Geoffrey Critzer, Apr 14 2023

V. Jovovic and G. Kilibarda, Enumeration of labeled initially-finally connected digraphs, Scientific review, Serbian Scientific Society, 19-20 (1996) 237-247.
R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

The unlabeled version is A051421.
Row sums of A057274.
Column k=1 of A361579.
Cf. A003027, A003029, A003030, A049524, A049414, A350792.

Initially(12) \\ See A057274. - Andrew Howroyd, Jan 11 2022

Corrected and extended by Vladeta Jovovic, Goran Kilibarda

Terms a(12) and beyond from Andrew Howroyd, Jan 11 2022

A049524 Number of digraphs with a source and a sink on n labeled nodes.

Original entry on oeis.org

1, 3, 48, 3424, 962020, 1037312116, 4344821892264, 71771421308713624, 4716467927380427847264, 1237465168798883061207535456, 1297923989772809185944542332007104, 5444330658513426322624322033259452670016, 91342931436147421630261703458729460990513248512

Offset: 1

Vladeta Jovovic, Goran Kilibarda

nonn

Here a source is defined to be a node which has a directed path to all other nodes and a sink to be a node to which all other nodes have a directed path. A digraph with a source and a sink can also be described as initially-finally connected. - Andrew Howroyd, Jan 16 2022

V. Jovovic, G. Kilibarda, Enumeration of labeled initially-finally connected digraphs, Scientific review, Serbian Scientific Society, 19-20 (1996), p. 244.

Andrew Howroyd, Table of n, a(n) for n = 1..50
Sean A. Irvine, Java program (github)
V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.
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.

The unlabeled version is A049531.
Row sums of A057271.
Cf. A003027, A003028, A003029, A003030, A049414, A350790.

InitFinally(15) \\ See A057271. - Andrew Howroyd, Jan 16 2022

Terms a(12) and beyond from Andrew Howroyd, Jan 16 2022

A003029 Number of unilaterally connected digraphs with n labeled nodes.

Original entry on oeis.org

1, 3, 48, 3400, 955860, 1034141596, 4340689156440, 71756043154026904, 4716284688998245793376, 1237457313794197125403483936, 1297922676419612772784598299454784, 5444329780242560941321703550018388707904, 91342929096228825123968637168641318872709897472

Offset: 1

N. J. A. Sloane

V. Jovovic, G. Kilibarda, Enumeration of labeled initially-finally connected digraphs, Scientific review, Serbian Scientific Society, 19-20 (1996), 237-247.
R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

The unlabeled version is A003088.
Row sums of A057275.
Cf. A003027, A003028, A003030, A049524, A049414.

Unilaterally(12) \\ See A057275. - Andrew Howroyd, Jan 19 2022

Corrected and extended by Vladeta Jovovic, Goran Kilibarda

Terms a(12) and beyond from Andrew Howroyd, Jan 11 2022

A049414 Number of quasi-initially connected digraphs with n labeled nodes.

Original entry on oeis.org

1, 3, 54, 3804, 1022320, 1065957628, 4389587378792, 72020744942708040, 4721708591209396542528, 1237892622263984613044109216, 1298060581376190776821670648395840

Offset: 1

Vladeta Jovovic, Goran Kilibarda

nonn

We say that a node v of a digraph is a quasi-source iff for every other node u there exists directed path from u to v or from v to u. A digraph with at least one quasi-source is called quasi-initially connected.

Sean A. Irvine, Java program (github)
V. Jovovic and G. Kilibarda, Enumeration of labeled quasi-initially connected digraphs, Discrete Math., 224 (2000), 151-163.

Cf. A003027, A003028, A003029, A003030.

Row sums of A057272.

The recurrence formulas are too long to be presented here.

A054947 Enumerates pairs consisting of a strongly connected labeled tournament and an arbitrary labeled tournament.

Original entry on oeis.org

1, 0, 16, 1536, 557056, 731381760, 3517947314176, 63491024068018176, 4399839304395507367936, 1190389701200990489133711360, 1270450770186900638201337522159616, 5381052721259860098970976735257549602816, 90765718885519516263620106778209295628266110976

Offset: 1

N. J. A. Sloane, May 24 2000

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 428, see b_n.

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A003030, A054946, A006125.

A054947 := proc(n)
    option remember;
    if n = 1 then
        1;
    else
        2^(n*(n-1))-add(binomial(n,t)*2^((n-1)*(n-t))*procname(t),t=1..n-1) ;
    end if;
end proc: # R. J. Mathar, May 10 2016

a[1] = 1; a[n_] := a[n] = 2^(n(n-1)) - Sum[Binomial[n, j] 2^((n-1)(n-j)) a[j], {j, 1, n-1}];
Array[a, 13] (* Jean-François Alcover, Aug 27 2019 *)

seq(n)={my(v=vector(n)); v[1]=1; for(n=2, #v, v[n]=2^(n*(n-1))-sum(j=1, n-1, binomial(n, j)*2^((n-1)*(n-j))*v[j])); v} \\ Andrew Howroyd, Sep 09 2018

a(n) = A054946(n) * A006125(n). - Andrew Howroyd, Jan 10 2022

More terms from Vladeta Jovovic, Mar 11 2003

A054948 Number of labeled semi-strong digraphs on n nodes.

Original entry on oeis.org

1, 1, 2, 22, 1688, 573496, 738218192, 3528260038192, 63547436065854848, 4400982906402148836736, 1190477715153930158152163072, 1270476960212865235273469079407872, 5381083212549793228422395071641588743168, 90765858793484859057065439213726376149311958016

Offset: 0

N. J. A. Sloane, May 24 2000

A digraph is semi-strong if all its weakly connected components are strongly connected. - Andrew Howroyd, Jan 14 2022

A digraph is semi-strong iff the following implication holds for all x,y in [n]: If there is a directed path from x to y then x and y are in the same strongly connected component. - Geoffrey Critzer, Oct 07 2023

Andrew Howroyd, Table of n, a(n) for n = 0..50
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

The unlabeled version is A350754.

Cf. A003030, A054947, A218393.

a[n_] := a[n] = Module[{A}, A = 1+Sum[a[k]*x^k/k!, {k, 1, n-1}]; n!*SeriesCoefficient[Sum[2^(k^2-k)*x^k/k!/(A /. x -> 2^k*x) , {k, 0, n}], {x, 0, n}]]; a[0]=1; Table[a[n], {n, 0, 13}] (* Jean-François Alcover, Dec 15 2014, after Paul D. Hanna *)

a(n)=local(A=1+sum(k=1,n-1,a(k)*x^k/k!)+x*O(x^n));n!*polcoeff(sum(k=0,n,2^(k^2-k)*x^k/k!/subst(A,x,2^k*x)),n)
for(n=0,10,print1(a(n),", ")) \\ Paul D. Hanna, Oct 27 2012

E.g.f.: 1/(1-B(x)) where B(x) is e.g.f. for A054947. - Vladeta Jovovic, Mar 11 2003
E.g.f. A(x) satisfies: Sum_{n>=0} 2^(n^2-n)*x^n/n! / A(2^n*x) = 1. - Paul D. Hanna, Oct 27 2012
E.g.f.: exp(B(x)) where B(x) is the e.g.f. of A003030. - Andrew Howroyd, Jan 14 2022

More terms from Vladeta Jovovic, Mar 11 2003

Changed offset to 0 and added a(0)=1 by Paul D. Hanna, Oct 27 2012

cp's OEIS Frontend

A035512 Number of unlabeled strongly connected digraphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions

A003027 Number of weakly connected digraphs with n labeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

Formula

Extensions

A057273 Triangle T(n,k) of the number of strongly connected digraphs on n labeled nodes and with k arcs, k=0..n*(n-1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

A070322 Number of primitive n X n real (0,1)-matrices.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A003028 Number of digraphs on n labeled nodes with a source.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A049524 Number of digraphs with a source and a sink on n labeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A003029 Number of unilaterally connected digraphs with n labeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions