A304074 Number of simple connected graphs with n nodes rooted at a pair of distinguished vertices.

0, 1, 4, 23, 162, 1549, 21090, 446061, 15673518, 961338288, 105752617892, 21155707801451, 7757777336382702, 5245054939576054088, 6571185585793205495484, 15325133281701584879975433, 66813349775478836190531605234, 546646811841381587823502759339055

Offset

1,3

Links

Andrew Howroyd, Table of n, a(n) for n = 1..50

Formula

a(n) = A304072(n) + A304073(n).

G.f.: 2*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

Example

a(3)=4: one choice to mark two roots in the triangular graph; one choice to mark the two leaves in the linear graph; two choices to mark the center node and a leave (1st root in the center or 2nd root in the center) in the linear graph.

Prog

(PARI)
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}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
cross(u, v) = {sum(i=1, #u, sum(j=1, #v, gcd(u[i], v[j])))}
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)!))}
seq(n)={my(g=Ser(S(n, []))); Vec(2*Ser(S(n, [1, 1]))/g - (Ser(S(n, [1]))/g)^2, -n)} \\ Andrew Howroyd, Sep 07 2019

Crossrefs

Cf. A001349 (not rooted), A303831 (vertices not distinguished), A304070 (not necessarily connected).

Cf. A000088, A000666.

Sequence in context: A263186 A245110 A342988 * A307402 A354497 A111547

Adjacent sequences: A304071 A304072 A304073 * A304075 A304076 A304077

Keyword

nonn

Author

Brendan McKay, May 05 2018

Extensions

Terms a(13) and beyond from Andrew Howroyd, Sep 07 2019

Status

approved