A003027 -id:A003027 - cp's OEIS frontend

A003085 Number of weakly connected digraphs with n unlabeled nodes.

1, 2, 13, 199, 9364, 1530843, 880471142, 1792473955306, 13026161682466252, 341247400399400765678, 32522568098548115377595264, 11366712907233351006127136886487, 14669074325902449468573755897547924182

Offset: 1

N. J. A. Sloane

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 124 and 241.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Keith Briggs, Table of n, a(n) for n = 1..64
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Alexander G. Ginsberg, Firing-Rate Models in Computational Neuroscience: New Applications and Methodologies, Ph. D. Dissertation, Univ. Michigan, 2023. See p. 7.
Martin Golubitsky and Yangyang Wang, Infinitesimal homeostasis in three-node input-output networks, Journal of Mathematical Biology (2020) Vol. 80, 1163-1185.
A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
X. Li, D. S. Stones, H. Wang, H. Deng, X. Liu and G. Wang, NetMODE: Network Motif Detection without Nauty, PLoS ONE 7(12): e50093. doi:10.1371/journal.pone.0050093. - From _N. J. A. Sloane_, Feb 02 2013
Eric Weisstein's World of Mathematics, Weakly Connected Digraph

Row sums of A054733.
Column sums of A350789.
The labeled case is A003027.
Cf. A000273, A003084, A035512 (strongly connected).

# The function EulerInvTransform is defined in A358451.
a := EulerInvTransform(A000273):
seq(a(n), n = 1..13); # Peter Luschny, Nov 21 2022

Needs["Combinatorica`"]; d[n_] := GraphPolynomial[n, x, Directed] /. x -> 1; max = 13; se = Series[ Sum[a[n]*x^n/n, {n, 1, max}] - Log[1 + Sum[ d[n]*x^n, {n, 1, max}]], {x, 0, max}]; sol = SolveAlways[ se == 0, x]; Do[ A003084[n] = a[n] /. sol[[1]], {n, 1, max}]; ClearAll[a, d]; a[n_] := (1/n)*Sum[ MoebiusMu[ n/d ] * A003084[d], {d, Divisors[n]} ]; Table[ a[n], {n, 1, max}] (* Jean-François Alcover, Feb 01 2012, after formula *)
terms = 13;
permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v - 1];
d[n_] := (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]} ]; s/n!);
A003084 = CoefficientList[Log[Sum[d[n] x^n, {n, 0, terms+1}]] + O[x]^(terms + 1), x] Range[0, terms] // Rest;
a[n_] := (1/n)*Sum[MoebiusMu[n/d] * A003084[[d]], {d, Divisors[n]}];
Table[a[n], {n, 1, terms}] (* Jean-François Alcover, Aug 30 2019, after Andrew Howroyd in A003084 *)

from functools import lru_cache
from itertools import product, combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A003085(n):
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<Chai Wah Wu, Jul 05 2024

a(n) = (1/n)*Sum_{d|n} mu(n/d)*A003084(d), where mu is Moebius function.

Inverse Euler transform of A000273. - Andrew Howroyd, Dec 27 2021

More terms from Vladeta Jovovic, Jan 09 2000

A062735 Triangular array T(n,k) giving number of weakly connected digraphs with n labeled nodes and k arcs (n >= 1, 0 <= k <= n(n-1)).

Original entry on oeis.org

1, 0, 2, 1, 0, 0, 12, 20, 15, 6, 1, 0, 0, 0, 128, 432, 768, 920, 792, 495, 220, 66, 12, 1, 0, 0, 0, 0, 2000, 11104, 33880, 73480, 123485, 166860, 184426, 167900, 125965, 77520, 38760, 15504, 4845, 1140, 190, 20, 1, 0, 0, 0, 0, 0, 41472, 337920, 1536000, 5062080

Offset: 1

Vladeta Jovovic, Jul 12 2001

			1;
0, 2, 1;
0, 0, 12, 20,   15,    6,      1;
0, 0, 0, 128,  432,  768,    920,    792,    495,    220,     66,    12, 1;
0, 0, 0,   0, 2000, 11104, 33880,  73480, 123485, 166860, 184426, 167900, ...;
0, 0, 0,   0,    0, 41472, 337920,1536000,5062080,.. ;
0, 0, 0,   0,    0,     0, 1075648,...

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 [math.CO], 2017; Table 76.

Cf. A003027 (row sums), A054733 (unlabeled case), A057273 (strongly connected), A097629 (diagonal), A123554 (not necessarily connected).

nn=7;s=Sum[(1+y)^(n^2-n) x^n/n!,{n,0,nn}];Range[0,nn]!CoefficientList[Series[Log[ s]+1,{x,0,nn}],{x,y}]//Grid  (* returns triangle indexed from n = 0, Geoffrey Critzer, Oct 07 2012 *)

row(n)={Vecrev(n!*polcoef(1 + log(sum(k=0, n, (1+y)^(k*(k-1))*x^k/k!, O(x*x^n))), n))}
{ for(n=0, 5, print(row(n))) } \\ Andrew Howroyd, Jan 11 2022

E.g.f.: 1+log( Sum_{n >= 0, k >= 0} binomial(n*(n-1), k)*x^n/n!*y^k ).

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

A054941 Number of weakly connected oriented graphs on n labeled nodes.

Original entry on oeis.org

1, 2, 20, 624, 55248, 13982208, 10358360640, 22792648882176, 149888345786341632, 2952810709943411146752, 174416705255313941476193280, 30901060796613886817249881227264, 16422801513633911416125344647746244608, 26183660776604240464418800095675915958222848

Offset: 1

N. J. A. Sloane, May 24 2000

The triangle of oriented labeled graphs on n>=1 nodes with 1<=k<=n components and row sums A047656 starts:
       1;
       2,      1;
      20,      6,     1;
     624,     92,    12,   1;
   55248,   3520,   260,  20,  1;
13982208, 354208, 11880, 580, 30, 1; - R. J. Mathar, Apr 29 2019

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

Row sums of A350732.
The unlabeled version is A086345.
Cf. A001187 (graphs), A003027 (digraphs), A350730 (strongly connected).

m:=30;
f:= func< x | (&+[3^Binomial(n,2)*x^n/Factorial(n) : n in [0..m+3]]) >;
R:=PowerSeriesRing(Rationals(), m);
Coefficients(R!(Laplace( Log(f(x)) ))); // G. C. Greubel, Apr 28 2023

nn=20; s=Sum[3^Binomial[n,2]x^n/n!,{n,0,nn}];
Drop[Range[0,nn]! CoefficientList[Series[Log[s]+1,{x,0,nn}],x],1] (* Geoffrey Critzer, Oct 22 2012 *)

N=20; x='x+O('x^N); Vec(serlaplace(log(sum(k=0, N, 3^binomial(k, 2)*x^k/k!)))) \\ Seiichi Manyama, May 18 2019

m=30
def f(x): return sum(3^binomial(n,2)*x^n/factorial(n) for n in range(m+4))
def A054941_list(prec):
    P. = PowerSeriesRing(QQ, prec)
    return P( log(f(x)) ).egf_to_ogf().list()
a=A054941_list(40); a[1:] # G. C. Greubel, Apr 28 2023

E.g.f.: log( Sum_{n >= 0} 3^binomial(n, 2)*x^n/n! ). - Vladeta Jovovic, Feb 14 2003

More terms from Vladeta Jovovic, Feb 14 2003

A062738 Number of connected labeled relations.

Original entry on oeis.org

1, 2, 12, 432, 61344, 32866560, 68307743232, 561981464819712, 18437720675374485504, 2417519433343618432696320, 1267602236528793479228867346432, 2658428102191640176274135259655176192, 22300681394917309655766001890404571062206464

Offset: 0

Vladeta Jovovic, Jul 12 2001

a(n) is the number of binary relations R on {1, 2, ..., n} such that the reflexive, symmetric, and transitive closure of R is the trivial relation.

T. D. Noe, Table of n, a(n) for n = 0..30

Cf. A003027.

a:= n-> n!*coeff(series(1+log(add(2^(i^2)*x^i/i!, i=0..n)), x, n+1), x, n):
seq(a(n), n=0..30); # Alois P. Heinz, Feb 16 2011

nn = 20; a = Sum[2^(n^2) x^n/n!, {n, 0, nn}]; Range[0, nn]! CoefficientList[Series[Log[a] + 1, {x, 0, nn}], x] (* Geoffrey Critzer, Oct 17 2011 *)

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

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

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.

A189898 Triangular array read by rows. T(n,k) is the number of digraphs with n labeled nodes having exactly k undirected (or weak) components, n >= 1, 1 <= k <= n.

Original entry on oeis.org

1, 3, 1, 54, 9, 1, 3834, 243, 18, 1, 1027080, 20790, 675, 30, 1, 1067308488, 6364170, 67635, 1485, 45, 1, 4390480193904, 7543111716, 23031540, 171045, 2835, 63, 1, 72022346388181584, 35217115838604, 30469951764, 63580545, 370440, 4914, 84, 1

Offset: 1

Geoffrey Critzer, May 01 2011

The Bell transform of A003027(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 18 2016

			1
3       1
54      9     1
3834    243   18   1
1027080 20790 675  30  1

Alois P. Heinz, Rows n = 1..32, flattened

Column 1 = A003027, row sums = A053763, lower diagonal = A045943.

T:= (n, k)-> coeff(series(log(add(2^(i^2-i) *x^i/i!, i=0..n))^k /k!,
                   x, n+1), x, n) *n!:
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, May 01 2011

a= Sum[4^Binomial[n,2]x^n/n!,{n,0,10}];
Transpose[Map[Drop[#, 1] &,Table[Range[0, 10]! CoefficientList[Series[Log[a]^n/n!, {x, 0, 10}], x], {n, 1, 10}]]] // Grid

# uses[bell_matrix from A264428, A003027]
# Adds a column 1,0,0,0, ... at the left side of the triangle.
bell_matrix(lambda n: A003027(n+1), 10) # Peter Luschny, Jan 18 2016

E.g.f. for column k: log(A(x))^k/k! where A(x) is the e.g.f. for A053763.

Name clarified by Andrew Howroyd, Jan 11 2022

A054593 Number of disconnected labeled digraphs with n nodes.

Original entry on oeis.org

0, 1, 10, 262, 21496, 6433336, 7566317200, 35247649746352, 648839620390462336, 47230175230392839683456, 13617860445102311268975051520, 15577054031612736747163633737901312

Offset: 1

Vladeta Jovovic, Apr 15 2000

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

The unlabeled case is A054590.

Cf. A003027, A053763 (not necessarily connected), A054592.

a(n) = 2^(n*(n-1)) - A003027(n).

cp's OEIS Frontend

A003085 Number of weakly connected digraphs with n unlabeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A062735 Triangular array T(n,k) giving number of weakly connected digraphs with n labeled nodes and k arcs (n >= 1, 0 <= k <= n(n-1)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A054941 Number of weakly connected oriented graphs on n labeled nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A062738 Number of connected labeled relations.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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