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,3

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.

Links

Table of n, a(n) for n=1..37.

Formula

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

Example

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

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

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, 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

Crossrefs

Cf. A008406.

Sequence in context: A097333 A001083 A173696 * A022864 A316075 A322429

Adjacent sequences: A120409 A120410 A120411 * A120413 A120414 A120415

Keyword

nonn

Author

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

Extensions

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

Status

approved