login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A126100 Number of rooted connected unlabeled graphs on n nodes. 6
0, 1, 1, 3, 11, 58, 407, 4306, 72489, 2111013, 111172234, 10798144310, 1944301471861, 650202565436890, 404697467417019634, 470133531223369393920, 1022561022228933341815171, 4177761667636803276899047351, 32163582481439081597751699343141, 468019937132164016636736323752098741 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Let G run through all connected unlabeled graphs on n nodes. Add up the numbers of inequivalent nodes (under Aut(G)) for each G.

"Pointed" connected graphs. This has the same relation to A001349 as A000081 does to A000055.

a(0) = 0 because the empty graph cannot be rooted.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..23 from David Applegate and N. J. A. Sloane)

FORMULA

The g.f. A(x) = x+x^2+3*x^3+11*x^4+... satisfies f(x) = 1 + A(x)*g(x), where f(x) = 1+x+2*x^2+6*x^3+20*x^4+... is the g.f. for A000666 and g(x) = 1+x+2*x^2+4*x^3+11*x^4+... is the g.f. for A000088. - Brendan McKay

EXAMPLE

For 3 nodes G is either a path (2 kinds of nodes) or a triangle (one kind of node), for a total of a(3) = 3.

For the 5-vertex graphs we have 2 x 1 orbit, 6 x 2 orbits, 8 x 3 orbits, 5 x 4 orbits for a total of 2 + 12 + 24 + 20 = 58.

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, 2]];

g[n_, r_] := (s = 0; Do[s += permcount[p]*(2^(r*Length[p] + edges[p])), {p, IntegerPartitions[n]}]; s/n!);

seq[m_] := Sum[g[n-1, 1] x^(n-1), {n, 0, m}]/Sum[g[n-1, 0] x^(n-1), {n, 0, m}] + O[x]^m // CoefficientList[#, x]& // Prepend[#, 0]&;

seq[20] (* Jean-Fran├žois Alcover, Jul 09 2018, after Andrew Howroyd *)

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

g(n, r) = {my(s=0); forpart(p=n, s+=permcount(p)*(2^(r*#p+edges(p)))); s/n!}

seq(n)={concat([0], Vec(Ser(vector(n, n, g(n-1, 1)))/Ser(vector(n, n, g(n-1, 0)))))} \\ Andrew Howroyd, May 03 2018

CROSSREFS

Cf. A001349, A126101, A000666, A000088, A126201, A303831 (birooted), A304311.

Sequence in context: A229512 A208990 A020012 * A009444 A305990 A168325

Adjacent sequences:  A126097 A126098 A126099 * A126101 A126102 A126103

KEYWORD

nonn,nice

AUTHOR

David Applegate and N. J. A. Sloane, Mar 05 2007

EXTENSIONS

a(5)-a(9) computed by Gordon F. Royle, Mar 05 2007

a(10) and a(11) computed by Brendan McKay, Mar 05 2007

a(12) onwards computed from the generating function, A000088 and A000666 by David Applegate and N. J. A. Sloane, Mar 06 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 22 10:58 EDT 2021. Contains 343174 sequences. (Running on oeis4.)