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,4

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

Formula

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

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

Prog

(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

Crossrefs

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

Sequence in context: A211037 A130607 A211042 * A295545 A309534 A348375

Adjacent sequences: A086342 A086343 A086344 * A086346 A086347 A086348

Keyword

nonn

Author

Eric W. Weisstein, Jul 16 2003

Extensions

More terms from Vladeta Jovovic, Jul 19 2003

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

Status

approved