cp's OEIS Frontend

A333865 Number of simple graphs on n nodes with vertex count > edge count + 1.

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