|
|
A333157
|
|
Triangle read by rows: T(n,k) is the number of n X n symmetric binary matrices with k ones in every row and column.
|
|
15
|
|
|
1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 10, 18, 10, 1, 1, 26, 112, 112, 26, 1, 1, 76, 820, 1760, 820, 76, 1, 1, 232, 6912, 35150, 35150, 6912, 232, 1, 1, 764, 66178, 848932, 1944530, 848932, 66178, 764, 1, 1, 2620, 708256, 24243520, 133948836, 133948836, 24243520, 708256, 2620, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
COMMENTS
|
T(n,k) is the number of k-regular symmetric relations on n labeled nodes.
T(n,k) is the number of k-regular graphs with half-edges on n labeled vertices.
Terms may be computed without generating all graphs by enumerating the number of graphs by degree sequence. A PARI program showing this technique is given below. Burnside's lemma as applied in A122082 and A000666 can be used to extend this method to the case of unlabeled vertices A333159 and A333161 respectively.
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = T(n,n-k).
|
|
EXAMPLE
|
Triangle begins:
1,
1, 1;
1, 2, 1;
1, 4, 4, 1;
1, 10, 18, 10, 1;
1, 26, 112, 112, 26, 1;
1, 76, 820, 1760, 820, 76, 1;
1, 232, 6912, 35150, 35150, 6912, 232, 1;
1, 764, 66178, 848932, 1944530, 848932, 66178, 764, 1;
...
|
|
PROG
|
(PARI) \\ See script in A295193 for comments.
GraphsByDegreeSeq(n, limit, ok)={
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(recurse(r, p, i, q, v, e) = if(e<=limit && poldegree(q)<=limit, if(i<0, if(ok(x^e+q, r), acc(x^e+q, v)), my(t=polcoeff(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)={my(M=GraphsByDegreeSeq(n, n\2, (p, r)->poldegree(p)-valuation(p, x) <= r + 1), v=vector(n+1)); for(i=1, matsize(M)[1], my(p=M[i, 1], d=poldegree(p)); v[1+d]+=M[i, 2]; if(pollead(p)==n, v[2+d]+=M[i, 2])); for(i=1, #v\2, v[#v+1-i]=v[i]); v}
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|