# compute the numbers of unlabelled graphs words(0): with(numtheory,mobius): with(numtheory,divisors): Z := proc(n) local i; options remember; expand(sum('s[i]*Z(n-i)','i'=1..n)/n); end: Z(0) := 1: pair := proc(t) local tm,id,ans,i,j,d,k; if type(t,`+`) then RETURN(map(pair,t)); fi; ans := sign(t) * content(t); tm := t/ans; id := convert(indets(tm),list); for i from 1 to nops(id) do d := degree(tm,id[i]); k := op(1,id[i]); if type(k,odd) then ans := ans * s[k]^(d*(k-1)/2); else ans := ans * s[k/2]^d * s[k]^(d*(k-2)/2); fi; ans := ans * s[k]^(k*d*(d-1)/2); od; for i from 1 to nops(id) do for j from i+1 to nops(id) do ans := ans * s[lcm(op(1,id[i]),op(1,id[j]))]^ (gcd(op(1,id[i]),op(1,id[j]))*degree(tm,id[i]) *degree(tm,id[j])); od; od; ans; end: # gy(n) = gf for graphs of order n by edges (variable y) gy := proc(n) local z,v,id; options remember; z := pair(Z(n)); id := indets(z); for v in id do z := subs(v=1+y^op(1,v),z); od; expand(z); end: bby := proc(n) local k; options remember; gy(n) - 1/n*sum('k*bby(k)*gy(n-k)','k'=1..n-1); expand(%); end: b := proc(n,m) options remember; coeff(bby(n),y,m); end: # g(n,m) := number of graphs with n vertices and m edges g := proc(n,m) options remember; if n < 1 then 0 else coeff(gy(n),y,m); fi; end: # allg(n) := total number of graphs with n vertices allg := proc(n) subs(y=1,gy(n)); end: # c(n,m) := number of connected graphs with n vertices and m edges c := proc(n,m) local r,ans; options remember; if n < 1 or m < 0 then 0 else ans := 0; for r in divisors(gcd(n,m)) do ans := ans + mobius(r) / r * b(n/r,m/r); od; ans; fi; end: