|
|
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.
a(0) = 0 because the empty graph cannot be rooted.
|
|
LINKS
|
|
|
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 * 1 orbit, 6 * 2 orbits, 8 * 3 orbits, 5 * 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]&;
|
|
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
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|