A139674 -id:A139674 - cp's OEIS frontend

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.

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

Offset: 0

Andrew Howroyd, Mar 09 2020

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.

			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;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..230

Columns k=0..8 are A000012, A000085, A000986, A110040, A139670, A139671, A139673, A139674, A139675.
Row sums are A322698.
Central coefficients are A333164.
Cf. A188448 (transposed as array).
Cf. A059441, A295193, A333158, A333159, A333161.

\\ 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}
for(n=0, 8, print(Row(n))) \\ Andrew Howroyd, Mar 14 2020

T(n,k) = T(n,n-k).

A188448 T(n,k)=Number of (n*k)Xk binary arrays with nonzero rows in decreasing order, no more than 2 ones in any row and exactly n ones in every column.

Original entry on oeis.org

1, 2, 0, 4, 1, 0, 10, 4, 0, 0, 26, 18, 1, 0, 0, 76, 112, 10, 0, 0, 0, 232, 820, 112, 1, 0, 0, 0, 764, 6912, 1760, 26, 0, 0, 0, 0, 2620, 66178, 35150, 820, 1, 0, 0, 0, 0, 9496, 708256, 848932, 35150, 76, 0, 0, 0, 0, 0, 35696, 8372754, 24243520, 1944530, 6912, 1, 0, 0, 0, 0

Offset: 1

R. H. Hardin Mar 31 2011

Table starts
.1.2.4.10..26...76...232.....764......2620........9496.........35696
.0.1.4.18.112..820..6912...66178....708256.....8372754.....108306280
.0.0.1.10.112.1760.35150..848932..24243520...805036704...30649435140
.0.0.0..1..26..820.35150.1944530.133948836.11234051976.1127512146540
.0.0.0..0...1...76..6912..848932.133948836.26615510712
.0.0.0..0...0....1...232...66178..24243520
.0.0.0..0...0....0.....1.....764
.0.0.0..0...0....0.....0
.0.0.0..0...0....0
.0.0.0..0...0

			All solutions for 9X3
..1..1..0
..1..0..1
..1..0..0
..0..1..1
..0..1..0
..0..0..1
..0..0..0
..0..0..0
..0..0..0

R. H. Hardin, Table of n, a(n) for n = 1..108

Row 1 is A000085
Row 2 is A000986
Row 3 is A110040
Row 4 is A139670
Row 5 is A139671
Row 6 is A139673
Row 7 is A139674
Row 8 is A139675

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula