|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
Table of n, a(n) for n=1..30.
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
Adjacent sequences: A333862 A333863 A333864 * A333866 A333867 A333868
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Eric W. Weisstein, Apr 08 2020
|
|
|
EXTENSIONS
|
Terms a(11) and beyond from Andrew Howroyd, Apr 08 2020
|
|
|
STATUS
|
approved
|
| |
|
|
