login
A333865
Number of simple graphs on n nodes with vertex count > edge count + 1.
0
0, 1, 2, 4, 8, 18, 40, 100, 256, 705, 2057, 6370, 20803, 71725, 259678, 985244, 3905022, 16124936, 69188809, 307765510, 1416146859, 6727549181, 32938379216, 165942445714, 859020421012, 4563322971706, 24847598243116, 138533012486423, 790075521708603, 4605183081182354
OFFSET
1,3
COMMENTS
These graphs correspond to "trivially ungraceful" graphs that do not have enough integers less than or equal to the edge count to cover all the vertices.
LINKS
Eric Weisstein's World of Mathematics, Graceful Graph
Eric Weisstein's World of Mathematics, Simple Graph
Eric Weisstein's World of Mathematics, Ungraceful Graph
FORMULA
a(n) <= A308556(n).
a(n) = Sum_{k=0..n-2} A008406(n, k). - Andrew Howroyd, Apr 08 2020
MATHEMATICA
Get["Combinatorica`"] // Quiet;
Table[Total[Take[CoefficientList[GraphPolynomial[n, x], x], n - 1]], {n, 20}]
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)))}
a(n)={my(s=0); if(n>1, forpart(p=n, s+=permcount(p)*polcoef(edges(p, i->1 + x^i + O(x^(n-1)))/(1-x), n-2) )); s/n!} \\ Andrew Howroyd, Apr 08 2020
CROSSREFS
Cf. A008406.
Cf. A308556 (number of simple ungraceful graphs on n nodes).
Sequence in context: A330052 A317787 A019231 * A274547 A112483 A151381
KEYWORD
nonn
AUTHOR
Eric W. Weisstein, Apr 08 2020
EXTENSIONS
Terms a(11) and beyond from Andrew Howroyd, Apr 08 2020
STATUS
approved