|
%I #19 Apr 09 2020 09:56:39
%S 0,1,2,4,8,18,40,100,256,705,2057,6370,20803,71725,259678,985244,
%T 3905022,16124936,69188809,307765510,1416146859,6727549181,
%U 32938379216,165942445714,859020421012,4563322971706,24847598243116,138533012486423,790075521708603,4605183081182354
%N Number of simple graphs on n nodes with vertex count > edge count + 1.
%C 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.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GracefulGraph.html">Graceful Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SimpleGraph.html">Simple Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/UngracefulGraph.html">Ungraceful Graph</a>
%F a(n) <= A308556(n).
%F a(n) = Sum_{k=0..n-2} A008406(n, k). - _Andrew Howroyd_, Apr 08 2020
%t Get["Combinatorica`"] // Quiet;
%t Table[Total[Take[CoefficientList[GraphPolynomial[n, x], x], n - 1]], {n, 20}]
%o (PARI)
%o 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}
%o 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)))}
%o 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
%Y Cf. A008406.
%Y Cf. A308556 (number of simple ungraceful graphs on n nodes).
%K nonn
%O 1,3
%A _Eric W. Weisstein_, Apr 08 2020
%E Terms a(11) and beyond from _Andrew Howroyd_, Apr 08 2020
|
