login
A327366
Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and minimum vertex-degree k.
6
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,7
COMMENTS
The minimum vertex-degree of the empty graph is infinity. It has been included here under k = 0. - Andrew Howroyd, Mar 09 2020
EXAMPLE
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
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}]
PROG
(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
CROSSREFS
Row sums are A006125.
Row sums without the first column are A006129.
Row sums without the first two columns are A100743.
Column k = 0 is A327367(n > 0).
Column k = 1 is A327227.
The unlabeled version is A294217.
Sequence in context: A316656 A083904 A215861 * A327069 A327334 A354794
KEYWORD
nonn,tabl
AUTHOR
Gus Wiseman, Sep 04 2019
EXTENSIONS
Terms a(28) and beyond from Andrew Howroyd, Sep 09 2019
STATUS
approved