A120412 Number of unlabeled graphs with n equal to the number of vertices plus the number of edges.

1, 1, 2, 2, 3, 5, 7, 10, 16, 25, 40, 66, 111, 191, 343, 627, 1182, 2301, 4609, 9511, 20229, 44252, 99564, 230171, 546118, 1328476, 3309876, 8436887, 21980376, 58473130, 158692559, 439012704, 1237049733, 3547984011, 10350963267, 30699209481, 92508993842

Offset: 1

Author

Petr Vojtechovsky (petr(AT)math.du.edu), Jul 05 2006

Keywords

• nonn

Comments

Given two integers p, q, one can count the different graphs having p vertices and q edges by the standard Polya counting technique. Our sequence is then obtained by summing up the terms with p + q = n.

Examples

			a(3) = 2 because there is a graph with 3 vertices and no edges and a graph with 2 vertices and one edge.
		

Crossrefs

Cf. A008406.

Programs

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_, t_] := Product[Product[g = GCD[v[[i]], v[[j]]]; t[v[[i]]*v[[j]]/g]^g, {j, 1, i - 1}], {i, 2, Length[v]}]*Product[c = v[[i]]; t[c]^Quotient[c-1, 2]*If[OddQ[c], 1, t[c/2]], {i, 1, Length[v]}];
row[n_] := row[n] = Module[{s = 0}, Do[s += permcount[p]*edges[p, 1+x^#&], {p, IntegerPartitions[n]}]; s/n!] // Expand // CoefficientList[#, x]&;
T[n_, k_] := If[k <= Length[row[n]], row[n][[k]], 0];
a[n_] := Sum[T[k, n-k+1], {k, 1, n}];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 37}] (* Jean-François Alcover, Jan 09 2021, after Andrew Howroyd in A008406 *)

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, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c-1)\2)*if(c%2, 1, t(c/2)))}
G(n, x)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i)); s/n!}
seq(n)={Vec(sum(k=1, n, x^k*G(k, x + O(x*x^(n-k)))))} \\ Andrew Howroyd, Nov 07 2019

Formula

a(n) = Sum_{i=1..n} A008406(i, n-i). - Andrew Howroyd, Nov 07 2019

Extensions

Terms a(14) and beyond from Andrew Howroyd, Nov 07 2019