# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a086345
Showing 1-1 of 1

%I A086345 #37 Oct 06 2025 23:48:14
%S A086345 1,1,1,5,34,535,20848,2120098,572849763,415361983540,815590925440865,
%T A086345 4373589784210012634,64535461714821630421106,
%U A086345 2637732191356603658136444467,300363258297687600380548275359231
%N A086345 Number of connected oriented graphs (i.e., connected directed graphs with no bidirected edges) on n nodes.
%H A086345 Andrew Howroyd, <a href="/A086345/b086345.txt">Table of n, a(n) for n = 0..50</a>
%H A086345 Musa Demirci, Ugur Ana, and Ismail Naci Cangul, <a href="https://doi.org/10.1007/978-981-16-1402-6">Properties of Characteristic Polynomials of Oriented Graphs</a>, Proc. Int'l Conf. Adv. Math. Comp. (ICAMC 2020) Springer, see p. 61.
%H A086345 Chathura Kankanamge, <a href="http://hdl.handle.net/10012/14051">Multiple Continuous Subgraph Query Optimization Using Delta Subgraph Queries</a>, Master Maths Thesis, Univ. of Waterloo, 2018.
%H A086345 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/OrientedGraph.html">Oriented Graph</a>
%F A086345 Inverse Euler transform of A001174. - _Andrew Howroyd_, Nov 03 2017
%t A086345 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];
%t A086345 edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total @ Quotient[v - 1, 2];
%t A086345 a1174[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!];
%t A086345 b = Array[a1174, 15];
%t A086345 mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
%t A086345 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]];
%t A086345 A086345 = EULERi[b] (* _Jean-François Alcover_, Jul 06 2018, after _Andrew Howroyd_ *)
%o A086345 (Python)
%o A086345 from fractions import Fraction
%o A086345 from functools import cache
%o A086345 from itertools import combinations
%o A086345 from math import factorial, gcd, prod
%o A086345 from sympy import divisors
%o A086345 from sympy.functions.combinatorial.numbers import mobius
%o A086345 from sympy.utilities.iterables import partitions
%o A086345 def A086345(n): return sum(mobius(d)*c(n//d) for d in divisors(n,generator=True))//n if n else 1
%o A086345 @cache
%o A086345 def b(n): return sum(Fraction(3**(sum(v1*v2*gcd(t1,t2) for (t1,v1),(t2,v2) in combinations(p.items(),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))
%o A086345 @cache
%o A086345 def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n)) # _Chai Wah Wu_, Jul 15 2024. Updated by _Hunter Hogan_, Oct 02 2025.
%Y A086345 Cf. A054941 (labeled case), A001174, A281446 (multisets).
%K A086345 nonn
%O A086345 0,4
%A A086345 _Eric W. Weisstein_, Jul 16 2003
%E A086345 More terms from _Vladeta Jovovic_, Jul 19 2003
%E A086345 a(0)=1 prepended by _Andrew Howroyd_, Sep 09 2018

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE
