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

%I #6 Aug 25 2017 23:38:13

%S 1,2,8,64,1024,27449,1052793,53470067,3451287371,275322712826,

%T 26566919914276,3047264283807562,409523561958024458,

%U 63703577287372238069,11351386036074641226649,2296295762734645223170899,523223196906671550193022083,133357299601279100522308107142

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

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

%H Andrew Howroyd, <a href="/A136283/b136283.txt">Table of n, a(n) for n = 1..50</a>

%o (PARI)

%o GraphsWithDegreeAtMost(n,limit)={

%o local(M=Map());

%o my(acc(p,v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v)));

%o 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)))));

%o my(iterate(v,k,f)=for(i=1,k,v=f(v));v);

%o 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]); }

%o a(n) = GraphsWithDegreeAtMost(n, 4); \\ _Andrew Howroyd_, Aug 25 2017

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

%K nonn

%O 1,2

%A _Don Knuth_, Mar 31 2008

%E Terms a(13) and beyond from _Andrew Howroyd_, Aug 25 2017