A304073 - OEIS

%I #16 Sep 08 2019 00:59:36

%S 0,0,1,8,67,701,10047,218083,7758105,478466565,52762737260,

%T 10566937121191,3876933205880431,2621875289142578194,

%U 3285187439267316978728,7662096100649423384254265,33405651855362295512020765765,273319227135047244053866187609854

%N Number of simple connected graphs with n nodes rooted at one oriented non-edge.

%H Andrew Howroyd, <a href="/A304073/b304073.txt">Table of n, a(n) for n = 1..50</a>

%F a(n) + A304072(n) = A304074(n).

%F G.f.: B(x)/G(x) - (x*C(x)/G(x))^2, where B(x) is the g.f. of A304069, C(x) is the g.f. of A000666 and G(x) is the g.f. of A000088. - _Andrew Howroyd_, Sep 07 2019

%e a(3)=1: no contribution from the triangle graph; one case of joining the leaves of the linear graph.

%e a(4)=8: we start from the 6 cases of non-oriented non-edges of A304071 and note two geometries where the orientation makes a difference: for the triangular graph with a protruding edge the orientation matters (to or from the leaf), and also for the linear graph with 4 nodes (to or from the leaf).

%o (PARI)

%o 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}

%o edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}

%o cross(u, v) = {sum(i=1, #u, sum(j=1, #v, gcd(u[i], v[j])))}

%o S(n, r)={my(t=#r+1); vector(n+1, n, if(n<t, 0, my(s=0); forpart(p=n-t, s+=permcount(p)*(2^(edges(p))*(2^cross(r, p)))); s/(n-t)!))}

%o seq(n)={my(g=Ser(S(n,[]))); Vec(Ser(S(n,[1,1]))/g - (Ser(S(n,[1]))/g)^2, -n)} \\ _Andrew Howroyd_, Sep 07 2019

%Y Cf. A001349 (not rooted), A304069 (not necessarily connected).

%Y Cf. A000088, A000666.

%K nonn

%O 1,4

%A _Brendan McKay_, May 05 2018

%E Terms a(13) and beyond from _Andrew Howroyd_, Sep 07 2019