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

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

Offset: 0

Author

Eric W. Weisstein, Jul 16 2003

Keywords

• nonn

Links

• 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

Crossrefs

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

Programs

Mathematica

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 *)

Python

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

Formula

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

Extensions

More terms from Vladeta Jovovic, Jul 19 2003

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