cp's OEIS Frontend

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

%I A086345 #32 Feb 16 2025 08:32:50
%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 functools import lru_cache
%o A086345 from itertools import combinations
%o A086345 from math import prod, factorial, gcd
%o A086345 from fractions import Fraction
%o A086345 from sympy.utilities.iterables import partitions
%o A086345 from sympy import mobius, divisors
%o A086345 def A086345(n):
%o A086345     @lru_cache(maxsize=None)
%o A086345     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)))
%o A086345     @lru_cache(maxsize=None)
%o A086345     def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o A086345     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
%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