A333164 -id:A333164 - 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).

A333165 Number of non-isomorphic 2n X 2n symmetric matrices with entries in {+1, -1} and all rows and columns summing to zero.

Original entry on oeis.org

1, 1, 2, 5, 66, 7937, 10211144, 133506398361, 18551599312980440, 28652629505982770906471, 510824181488832447063505273252

Offset: 0

Andrew Howroyd, Mar 11 2020

a(n) is the number of non-isomorphic 2n X 2n symmetric binary matrices with n ones in every row and column.

			The a(1) = 1 matrix is:
  [+ -]
  [- +]
The a(2) = 2 matrices are:
  [+ + - -]   [+ + - -]
  [+ + - -]   [+ - + -]
  [- - + +]   [- + - +]
  [- - + +]   [- - + +]

Central coefficients of A333159.

Cf. A333164, A333166.

a(n) = A333159(2*n, n).

A333166 Number of n-regular graphs on 2n unlabeled vertices with half-edges.

Original entry on oeis.org

1, 2, 3, 12, 118, 9638, 10622074, 135037240786, 18621890255342234, 28688490385422625653266, 511030957184968000138445253202

Offset: 0

Andrew Howroyd, Mar 12 2020

A half-edge is like a loop except it only adds 1 to the degree of its vertex.

a(n) is the number of non-isomorphic 2n X 2n symmetric matrices with entries in {+1, -1} and all rows and columns summing to zero where isomorphism is up to simultaneous permutation of rows and columns. The case where rows and columns can be permuted independently is covered by A333165.

			The a(1) = 1 matrix is:
  [+ -]
  [- +]
.
The a(2) = 2 matrices are:
  [+ + - -]   [- - + +]   [+ + - -]
  [+ + - -]   [- - + +]   [+ - + -]
  [- - + +]   [+ + - -]   [- + - +]
  [- - + +]   [+ + - -]   [- - + +]

Central coefficients of A333161.

a(n) = A333161(2*n, n).

Cf. A333164, A333165.

A213793 Number of n X n 0..1 symmetric arrays with every row summing to floor(n/2).

Original entry on oeis.org

1, 1, 2, 4, 18, 112, 1760, 35150, 1944530, 133948836, 26615510712, 6549149852112, 4762109992158288, 4274712091685443584, 11528251571501588791296, 38295413179145036856212700, 386860001875783390762182911250, 4805622573099374975572752075805000

Offset: 0

R. H. Hardin, Jun 20 2012

nonn

			Some solutions for n=4
..1..1..0..0....0..0..1..1....0..1..1..0....1..0..1..0....0..1..1..0
..1..0..1..0....0..0..1..1....1..0..0..1....0..0..1..1....1..1..0..0
..0..1..0..1....1..1..0..0....1..0..0..1....1..1..0..0....1..0..0..1
..0..0..1..1....1..1..0..0....0..1..1..0....0..1..0..1....0..0..1..1

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

Column 1 of A213800.

Cf. A333164.

a(2*n) = A333164(n). - Andrew Howroyd, Apr 08 2020

a(0)=1 prepended and terms a(13) and beyond from Andrew Howroyd, Apr 08 2020

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

A333165 Number of non-isomorphic 2n X 2n symmetric matrices with entries in {+1, -1} and all rows and columns summing to zero.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A333166 Number of n-regular graphs on 2n unlabeled vertices with half-edges.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A213793 Number of n X n 0..1 symmetric arrays with every row summing to floor(n/2).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions