A086345 -id:A086345 - cp's OEIS frontend

A001174 Number of oriented graphs (i.e., digraphs with no bidirected edges) on n unlabeled nodes. Also number of complete digraphs on n unlabeled nodes. Number of antisymmetric relations (i.e., oriented graphs with loops) on n unlabeled nodes is A083670.

1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, 816007449011040, 4374406209970747314, 64539836938720749739356, 2637796735571225009053373136, 300365896158980530053498490893399

Offset: 1

N. J. A. Sloane

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 133, c_p.
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sept. 15, 1955, pp. 14-22.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
Musa Demirci, Ugur Ana, and Ismail Naci Cangul, Properties of Characteristic Polynomials of Oriented Graphs, Proc. Int'l Conf. Adv. Math. Comp. (ICAMC 2020) Springer, see p. 60.
F. Harary and E. M. Palmer, Enumeration of mixed graphs, Proc. Amer. Math. Soc., 17 (1966), 682-687.
T. R. Hoffman and J. P. Solazzo, Complex Two-Graphs via Equiangular Tight Frames, arXiv preprint arXiv:1408.0334 [math.CO], 2014-2017.
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Eric Weisstein's World of Mathematics, Oriented Graph

Cf. A000595, A001173, A281446.

Cf. A047656 (labeled case), A054941 (connected labeled case), A086345 (connected unlabeled case).

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[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total @ Quotient[v - 1, 2];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Array[a, 15] (* Jean-François Alcover, Jul 06 2018, after Andrew Howroyd *)

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}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, (v[i]-1)\2)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)); s/n!} \\ Andrew Howroyd, Oct 23 2017

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A001174(n): return int(sum(Fraction(3**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q-1>>1)*r+(q*r*(r-1)>>1) for q, r in p.items())),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 15 2024

There's an explicit formula - see for example Harary and Palmer (book), Eq. (5.4.14).

a(n) ~ 3^(n*(n-1)/2)/n! [McIlroy, 1955]. - Vaclav Kotesovec, Dec 19 2016

More terms from Vladeta Jovovic

Revised description from Vladeta Jovovic, Jan 20 2005

A350489 Number of strongly connected oriented graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 0, 1, 4, 76, 4232, 611528, 222688092, 205040866270, 484396550160186, 2987729989350536868, 48933147333828638153224, 2160018687398735805070288200, 260218032038985813416099131315377, 86440094822917159858790627703492969772

Offset: 0

Andrew Howroyd, Jan 01 2022

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50
Andrew Howroyd, PARI Program, Jan 2022.
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.
Wikipedia, Strongly connected component

Row sums of A350750.
The labeled version is A350730.
Cf. A001174, A035512, A086345, A350751.

A350489seq(15) \\ See Links for program code.

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

A350734 Triangle read by rows: T(n,k) is the number of weakly connected oriented graphs on n unlabeled nodes with k arcs, n >= 1, k = 0..n*(n-1)/2.

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 2, 0, 0, 0, 8, 12, 10, 4, 0, 0, 0, 0, 27, 68, 127, 144, 107, 50, 12, 0, 0, 0, 0, 0, 91, 395, 1144, 2393, 3767, 4500, 4112, 2740, 1274, 376, 56, 0, 0, 0, 0, 0, 0, 350, 2170, 9139, 28606, 71583, 145600, 244589, 339090, 387458, 361394, 271177, 159872, 71320, 22690, 4604, 456

Offset: 1

Andrew Howroyd, Jan 13 2022

			Triangle begins:
  [1] 1;
  [2] 0, 1;
  [3] 0, 0, 3, 2;
  [4] 0, 0, 0, 8, 12, 10,   4;
  [5] 0, 0, 0, 0, 27, 68, 127, 144, 107, 50, 12;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1350 (rows 1..20)

Row sums are A086345.
Column sums are A350915.
Leading diagonal is A000238.
The labeled version is A350732.
Cf. A054733, A350733, A350750, A350914 (transpose).

InvEulerMTS(p)={my(n=serprec(p,x)-1, q=log(p), vars=variables(p)); sum(i=1, n, moebius(i)*substvec(q + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i)}
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}
edges(v, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c-1)\2))}
G(n, x)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+2*x^i)); s/n!}
row(n)={Vecrev(polcoef(InvEulerMTS(sum(i=0, n, G(i, y)*x^i, O(x*x^n))), n))}
{ for(n=1, 6, print(row(n))) }

A350914 Triangle read by rows: T(n,k) is the number of unlabeled weakly connected oriented graphs with n arcs and k vertices, k = 1..n+1.

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 0, 0, 2, 8, 0, 0, 0, 12, 27, 0, 0, 0, 10, 68, 91, 0, 0, 0, 4, 127, 395, 350, 0, 0, 0, 0, 144, 1144, 2170, 1376, 0, 0, 0, 0, 107, 2393, 9139, 11934, 5743, 0, 0, 0, 0, 50, 3767, 28606, 67104, 64892, 24635, 0, 0, 0, 0, 12, 4500, 71583, 288331, 468702, 352286, 108968

Offset: 0

Andrew Howroyd, Jan 29 2022

			Triangle begins:
  1;
  0, 1;
  0, 0, 3;
  0, 0, 2,  8;
  0, 0, 0, 12,  27;
  0, 0, 0, 10,  68,   91;
  0, 0, 0,  4, 127,  395,  350;
  0, 0, 0,  0, 144, 1144, 2170, 1376;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Row sums are A350915.
Column sums are A086345.
Cf. A350734 (transpose), A350789 (digraphs).

\\ See A350734 for G, InvEulerMTS.
T(n)={my(p=InvEulerMTS(sum(i=0, n, G(i, y+O(y^n))*x^i, O(x*x^n)))); vector(n, n, Vec(O(x^n)+polcoef(p,n-1,y)/x, -n))}
{ my(A=T(10)); for(n=1, #A, print(A[n])) }

A350915 Number of weakly connected oriented graphs with n arcs.

Original entry on oeis.org

1, 1, 3, 10, 39, 169, 876, 4834, 29316, 189054, 1294382, 9321232, 70326820, 553433559, 4528840412, 38432156859, 337454775045, 3059843449398, 28602687303185, 275222034228537, 2722343346822614, 27647618196693537, 287970349621911635, 3073082817450997700, 33568654163238906968

Offset: 0

Andrew Howroyd, Jan 29 2022

nonn

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

Row sums of A350914.
Column sums of A350734.
Cf. A053454, A086345.

\\ See A350734 for G, InvEulerMTS.
seq(n)=Vec(subst(Pol(InvEulerMTS(sum(i=0, n, G(i, y+O(y^n))*x^i, O(x*x^n)))), x, 1))

A101460 Number of connected antisymmetric relations on n unlabeled nodes.

Original entry on oeis.org

1, 2, 4, 32, 467, 15726, 1283648, 266995482, 145658273814, 212067643326874, 834200554714504905, 8952922576975709358534, 264287923205519914989471726, 21606715274151098406493353524694, 4921011141817073607674347572008576367

Offset: 0

Vladeta Jovovic, Jan 20 2005

nonn

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

Cf. A083670, A086345, A001174.

Inverse Euler transform of A083670. - Andrew Howroyd, Oct 24 2019

A281446 Triangle read by rows: Number of oriented graphs on n nodes with k components.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 5, 1, 1, 0, 34, 6, 1, 1, 0, 535, 39, 6, 1, 1, 0, 20848, 584, 40, 6, 1, 1, 0, 2120098, 21553, 589, 40, 6, 1, 1, 0, 572849763, 2144216, 21602, 590, 40, 6, 1, 1, 0, 415361983540, 575092291, 2144956, 21607, 590, 40, 6, 1, 1, 0, 815590925440865, 415946286005, 575116919, 2145005, 21608

Offset: 0

R. J. Mathar, Apr 13 2017

Multiset transform of A086345.

			1;
0,1;
0,1,1;
0,5,1,1;
0,34,6,1,1;
0,535,39,6,1,1;
0,20848,584,40,6,1,1;
0,2120098,21553,589,40,6,1,1;
0,572849763,2144216,21602,590,40,6,1,1;
0,415361983540,575092291,2144956,21607,590,40,6,1,1;

Index entries for triangles generated by the Multiset Transformation

Cf. A086345 (column 1), A001174 (row sums).

G.f.: Product_{j>=1} (1-y*x^j)^(-A086345(j)). - Alois P. Heinz, Apr 13 2017

cp's OEIS Frontend

A001174 Number of oriented graphs (i.e., digraphs with no bidirected edges) on n unlabeled nodes. Also number of complete digraphs on n unlabeled nodes. Number of antisymmetric relations (i.e., oriented graphs with loops) on n unlabeled nodes is A083670.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A350489 Number of strongly connected oriented graphs on n unlabeled nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A350734 Triangle read by rows: T(n,k) is the number of weakly connected oriented graphs on n unlabeled nodes with k arcs, n >= 1, k = 0..n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A350914 Triangle read by rows: T(n,k) is the number of unlabeled weakly connected oriented graphs with n arcs and k vertices, k = 1..n+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A350915 Number of weakly connected oriented graphs with n arcs.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A101460 Number of connected antisymmetric relations on n unlabeled nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

A281446 Triangle read by rows: Number of oriented graphs on n nodes with k components.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula