A327366 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and minimum vertex-degree k.
1, 1, 0, 1, 1, 0, 4, 3, 1, 0, 23, 31, 9, 1, 0, 256, 515, 227, 25, 1, 0, 5319, 15381, 10210, 1782, 75, 1, 0, 209868, 834491, 815867, 221130, 15564, 231, 1, 0, 15912975, 83016613, 116035801, 47818683, 5499165, 151455, 763, 1, 0, 2343052576, 15330074139, 29550173053, 18044889597, 3291232419, 158416629, 1635703, 2619, 1, 0
Offset: 0
Examples
Triangle begins:
1
1 0
1 1 0
4 3 1 0
23 31 9 1 0
256 515 227 25 1 0
5319 15381 10210 1782 75 1 0
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..230 (rows n = 0..20)
- Gus Wiseman, The graphs with 4 vertices and minimum vertex-degree k (row n = 4).
Crossrefs
Programs
-
Mathematica
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],k==If[#=={}||Union@@#!=Range[n],0,Min@@Length/@Split[Sort[Join@@#]]]&]],{n,0,5},{k,0,n}] -
PARI
GraphsByMaxDegree(n)={ local(M=Map(Mat([x^0, 1]))); my(acc(p, v)=my(z); mapput(M, p, if(mapisdefined(M, p, &z), z+v, v))); my(merge(r, p, v)=acc(p + sum(i=1, poldegree(p)-r-1, polcoef(p, i)*(1-x^i)), v)); my(recurse(r, p, i, q, v, e)=if(i<0, merge(r, x^e+q, v), my(t=polcoef(p, i)); for(k=0, t, self()(r, p, i-1, (t-k+x*k)*x^i+q, binomial(t, k)*v, e+k)))); for(k=2, n, my(src=Mat(M)); M=Map(); for(i=1, matsize(src)[1], my(p=src[i, 1]); recurse(n-k, p, poldegree(p), 0, src[i, 2], 0))); Mat(M); } Row(n)={if(n==0, [1], my(M=GraphsByMaxDegree(n), u=vector(n+1)); for(i=1, matsize(M)[1], u[n-poldegree(M[i,1])]+=M[i,2]); u)} { for(n=0, 8, print(Row(n))) } \\ Andrew Howroyd, Mar 09 2020
Extensions
Terms a(28) and beyond from Andrew Howroyd, Sep 09 2019
Comments