A136283 Number of graphs on n labeled nodes with degree at most 4.

1, 2, 8, 64, 1024, 27449, 1052793, 53470067, 3451287371, 275322712826, 26566919914276, 3047264283807562, 409523561958024458, 63703577287372238069, 11351386036074641226649, 2296295762734645223170899, 523223196906671550193022083, 133357299601279100522308107142

Offset: 1

Author

Don Knuth, Mar 31 2008

Keywords

• nonn

References

• D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.4.

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..50

Crossrefs

Cf. A000085 (degree at most 1), A136281-A136286.

Programs

PARI

GraphsWithDegreeAtMost(n,limit)={
local(M=Map());
my(acc(p,v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));
my(recurse(p,i,q,v,e)=if(e<=limit&&poldegree(q)<=limit, if(i<0, acc(x^e+q, v), my(t=polcoeff(p,i)); for(k=0, t, self()(p, i-1, (t-k+x*k)*x^i+q, binomial(t,k)*v, e+k)))));
my(iterate(v,k,f)=for(i=1,k,v=f(v));v);
vecsum(Vec(iterate(Mat([1,1]), n-1, src->M=Map(); for(i=1, matsize(src)[1], my(p=src[i,1]); recurse(p,poldegree(p),0,src[i,2],0)); Mat(M)))[2]); }
a(n) = GraphsWithDegreeAtMost(n, 4); \\ Andrew Howroyd, Aug 25 2017

Extensions

Terms a(13) and beyond from Andrew Howroyd, Aug 25 2017