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

A086345 Number of connected oriented graphs (i.e., connected directed graphs with no bidirected edges) on n nodes.

Original entry on oeis.org

1, 1, 1, 5, 34, 535, 20848, 2120098, 572849763, 415361983540, 815590925440865, 4373589784210012634, 64535461714821630421106, 2637732191356603658136444467, 300363258297687600380548275359231

Offset: 0

Eric W. Weisstein, Jul 16 2003

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50
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. 61.
Chathura Kankanamge, Multiple Continuous Subgraph Query Optimization Using Delta Subgraph Queries, Master Maths Thesis, Univ. of Waterloo, 2018.
Eric Weisstein's World of Mathematics, Oriented Graph

Cf. A054941 (labeled case), A001174, A281446 (multisets).

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];
a1174[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!];
b = Array[a1174, 15];
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
A086345 = EULERi[b] (* Jean-François Alcover, Jul 06 2018, after Andrew Howroyd *)

from functools import lru_cache
from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
from sympy import mobius, divisors
def A086345(n):
    @lru_cache(maxsize=None)
    def b(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)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
    return sum(mobius(d)*c(n//d) for d in divisors(n,generator=True))//n if n else 1 # Chai Wah Wu, Jul 15 2024

Inverse Euler transform of A001174. - Andrew Howroyd, Nov 03 2017

More terms from Vladeta Jovovic, Jul 19 2003

a(0)=1 prepended by Andrew Howroyd, Sep 09 2018

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

Original entry on oeis.org

1, 0, 2, 0, 0, 12, 8, 0, 0, 0, 128, 240, 192, 64, 0, 0, 0, 0, 2000, 7104, 13120, 15360, 11520, 5120, 1024, 0, 0, 0, 0, 0, 41472, 234240, 729600, 1578240, 2531840, 3068928, 2795520, 1863680, 860160, 245760, 32768

Offset: 1

Andrew Howroyd, Jan 11 2022

			Triangle begins:
  [1] 1;
  [2] 0, 2;
  [3] 0, 0, 12,   8;
  [4] 0, 0,  0, 128,  240,  192,    64;
  [5] 0, 0,  0,   0, 2000, 7104, 13120, 15360, 11520, 5120, 1024;
  ...

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

Row sums are A054941.
The leading diagonal is A097629.
The unlabeled version is A350734.
Cf. A062735 (digraphs), A350731 (strongly connected).

row(n)={Vecrev(n!*polcoef(1 + log(sum(k=0, n, (1+2*y)^(k*(k-1)/2)*x^k/k!, O(x*x^n))), n))}
{ for(n=1, 5, print(row(n))) }

A350730 Number of strongly connected oriented graphs on n labeled nodes.

Original entry on oeis.org

1, 0, 2, 66, 7998, 2895570, 3015624078, 8890966977354, 74079608267459142, 1754419666770364130730, 119163820122708911990211222, 23431180614718394105521543222866, 13448652672256961901980839022683943838, 22684139279519345808802725789494254587951810

Offset: 1

Andrew Howroyd, Jan 11 2022

nonn

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

The unlabeled version is A350489.
Row sums of A350731.
Cf. A003030, A054941.

StrongO(14) \\ See A350731 for program code.

A177780 E.g.f. satisfies: L(x) = xSum_{n>=0} (2^n/n!)Product_{k=0..n-1} L(3^k*x).

Original entry on oeis.org

1, 4, 60, 2496, 276240, 83893248, 72508524480, 182341191057408, 1348995112077074688, 29528107099434111467520, 1918583757808453356238126080, 370812729559366641806998574727168

Offset: 1

Paul D. Hanna, May 20 2010

nonn

More generally, we have the following conjecture.
Define the series E(,) and L(,) by:
  E(x,q) = Sum_{n>=0} q^(n(n-1)/2)*x^n/n!,
 L(x,q) = x*d/dx log(E(x,q)) = x*E'(x,q)/E(x,q),
then L(x,q) satisfies:
  L(x,q) = x*Sum_{n>=0} (q-1)^n/n! * Product_{k=0..n-1} L(q^k*x,q),
 1/E(x,q) = Sum_{n>=0} (-1)^n/n! * Product_{k=0..n-1} L(q^k*x,q).

			E.g.f.: L(x) = x + 4*x^2/2! + 60*x^3/3! + 2496*x^4/4! + 276240*x^5/5! + ... + n*A054941(n)*x^n/n! + ...
Given the related expansions:
  E(x) = 1 + x + 3*x^2/2! + 27*x^3/3! + 729*x^4/4! + 59049*x^5/5! + ...
  log(E(x)) = x + 2*x^2/2! + 20*x^3/3! + 624*x^4/4! + 55248*x^5/5! + ... + A054941(n)*x^n/n! + ...
then L(x) satisfies:
  L(x)/x = 1 + 2*L(x) + 2^2*L(x)L(3x)/2! + 2^3*L(x)L(3x)L(9x)/3! + 2^4*L(x)L(3x)L(9x)L(27x)/4! + ...
  1/E(x) = 1 - L(x) + L(x)L(3x)/2! - L(x)L(3x)L(9x)/3! + L(x)L(3x)L(9x)L(27x)/4! -+ ...

Cf. A054941, A177779, A177777, A177781.

m = 13; A[] = 0; Do[A[x] = x Sum[2^n/n! Product[A[3^k x], {k, 0, n-1}], {n, 0, m}] + O[x]^m // Normal, {m}]; CoefficientList[A[x]/x, x] * Range[1, m-1]! (* Jean-François Alcover, Nov 03 2019 *)

{a(n,q=3)=local(Lq=x+x^2);for(i=1,n,Lq=x*sum(m=0,n,(q-1)^m/m!*prod(k=0,m-1,subst(Lq,x,q^k*x+x*O(x^n)))));n!*polcoeff(Lq,n)}

a(n) = n*A054941(n), where A054941(n) is the number of connected oriented graphs on n nodes.
Define the series E(x) and L(x) by:
  E(x) = Sum_{n>=0} 3^(n(n-1)/2)*x^n/n!,
  L(x) = x*d/dx log(E(x)) = x*E'(x)/E(x),
then L(x) satisfies:
  L(x) = x*Sum_{n>=0} 2^n/n! * Product_{k=0..n-1} L(3^k*x),
  1/E(x) = Sum_{n>=0} (-1)^n/n! * Product_{k=0..n-1} L(3^k*x).

A054942 Number of connected oriented graphs on n nodes with an even number of edges.

Original entry on oeis.org

1, 0, 12, 304, 27664, 6990848, 5179182272, 11396324423680, 74944172893348096, 1476405354971703541760, 87208352627656970763963392, 15450530398306943408624578330624, 8211400756816955708062672329408385024

Offset: 1

N. J. A. Sloane, May 24 2000

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. A000831, A054941, A054943.

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)*(Cos(x) + Sin(x)))/2 ))); // G. C. Greubel, Apr 29 2023

nn = 15; g[z] := Sum[(1 + 2 u)^Binomial[n, 2] z^n/n!, {n, 0, nn}]; Drop[
Map[Total[#[[1 ;; Binomial[nn, 2] + 1 ;;2]]]&,Range[0,nn]!CoefficientList[
Series[Log[g[z]], {z, 0, nn}], {z, u}]], 1] (* Geoffrey Critzer, Jul 28 2016 *)

seq(n)={my(A=O(x*x^n)); Vec(serlaplace(log(sum(k=0, n, 3^binomial(k, 2)*x^k/k!) + A) + log(cos(x + A) + sin(x + A)))/2)} \\ Andrew Howroyd, Sep 10 2018

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)*(cos(x) + sin(x)))/2 ).egf_to_ogf().list()
a=A054941_list(40); a[1:] # G. C. Greubel, Apr 29 2023

a(n) = (A054941(n) - (-1)^n*A000831(n-1))/2. - Andrew Howroyd, Sep 10 2018

E.g.f.: log(f(x)*(cos(x) + sin(x))), where f(x) = Sum_{j >= 0} 3^binomial(j, 2)*x^j/j!. - G. C. Greubel, Apr 29 2023

More terms from Vladeta Jovovic, Mar 11 2003

A054943 Number of connected oriented graphs on n nodes with an odd number of edges.

Original entry on oeis.org

0, 2, 8, 320, 27584, 6991360, 5179178368, 11396324458496, 74944172892993536, 1476405354971707604992, 87208352627656970712229888, 15450530398306943408625302896640, 8211400756816955708062672318337859584

Offset: 1

N. J. A. Sloane, May 24 2000

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. A000831, A054941, A054942.

nn = 15; g[z] :=Sum[(1 + 2 u)^Binomial[n, 2] z^n/n!, {n, 0, nn}]; Drop[
Map[Total[#[[2 ;; Binomial[nn, 2] + 1 ;;2]]]&,Range[0,nn]!CoefficientList[
Series[Log[g[z]], {z, 0, nn}], {z, u}]], 1] (* Geoffrey Critzer, Jul 28 2016 *)

seq(n)={my(A=O(x*x^n)); Vec(serlaplace(log(sum(k=0, n, 3^binomial(k, 2)*x^k/k!) + A) - log(cos(x + A) + sin(x + A)))/2, -n)} \\ Andrew Howroyd, Sep 10 2018

a(n) = (A054941(n) + (-1)^n*A000831(n-1))/2. - Andrew Howroyd, Sep 10 2018

More terms from Vladeta Jovovic, Mar 11 2003

A308458 Expansion of e.g.f. log(Sum_{k>=0} k^binomial(k,2) * x^k / k!).

Original entry on oeis.org

1, 1, 23, 3994, 9745169, 470126386536, 558542572785461515, 19342808645467142112096240, 22528399370853856386499346950471953, 999999999774716004550606847948627702867525440, 1890591424701781041871514584507296209311760279398415565711

Offset: 1

Seiichi Manyama, May 27 2019

nonn

			E.g.f.: x + x^2/2! + 23*x^3/3! + 3994*x^4/4! + 9745169*x^5/5! + 470126386536*x^6/6! + 558542572785461515*x^7/7! + ... .

Seiichi Manyama, Table of n, a(n) for n = 1..36

Cf. A001187, A001865, A003027, A054941.

N=20; x='x+O('x^N); Vec(serlaplace(log(sum(k=0, N, k^binomial(k, 2)*x^k/k!))))

A308460 Square array A(n,k), n >= 1, k >= 1, read by antidiagonals, where column k is the expansion of e.g.f. log(Sum_{j>=0} k^binomial(j,2) * x^j/j!).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 4, 0, 1, 3, 20, 38, 0, 1, 4, 54, 624, 728, 0, 1, 5, 112, 3834, 55248, 26704, 0, 1, 6, 200, 15104, 1027080, 13982208, 1866256, 0, 1, 7, 324, 45750, 9684224, 1067308488, 10358360640, 251548592, 0, 1, 8, 490, 116208, 60225000, 30458183680, 4390480193904, 22792648882176, 66296291072, 0

Offset: 1

Seiichi Manyama, May 28 2019

			Square array begins:
   1,     1,        1,          1,           1, ...
   0,     1,        2,          3,           4, ...
   0,     4,       20,         54,         112, ...
   0,    38,      624,       3834,       15104, ...
   0,   728,    55248,    1027080,     9684224, ...
   0, 26704, 13982208, 1067308488, 30458183680, ...

Seiichi Manyama, Antidiagonals n = 1..50, flattened

Columns k=1..4 give A000007(n-1), A001187, A054941, A003027.

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

A086345 Number of connected oriented graphs (i.e., connected directed graphs with no bidirected edges) on n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A350730 Number of strongly connected oriented graphs on n labeled nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A177780 E.g.f. satisfies: L(x) = x*Sum_{n>=0} (2^n/n!)*Product_{k=0..n-1} L(3^k*x).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A054942 Number of connected oriented graphs on n nodes with an even number of edges.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A054943 Number of connected oriented graphs on n nodes with an odd number of edges.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A308458 Expansion of e.g.f. log(Sum_{k>=0} k^binomial(k,2) * x^k / k!).

Views

Author

A177780 E.g.f. satisfies: L(x) = xSum_{n>=0} (2^n/n!)Product_{k=0..n-1} L(3^k*x).