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

A333159 Triangle read by rows: T(n,k) is the number of non-isomorphic n X n symmetric binary matrices with k ones in every row and column up to permutation of rows and columns.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 4, 5, 4, 1, 1, 1, 1, 4, 12, 12, 4, 1, 1, 1, 1, 7, 31, 66, 31, 7, 1, 1, 1, 1, 8, 90, 433, 433, 90, 8, 1, 1, 1, 1, 12, 285, 3442, 7937, 3442, 285, 12, 1, 1, 1, 1, 14, 938, 30404, 171984, 171984, 30404, 938, 14, 1, 1

Offset: 0

Andrew Howroyd, Mar 10 2020

Rows and columns may be permuted independently. The case that rows and columns must be permuted together is covered by A333161.

T(n,k) is the number of k-regular bicolored graphs on 2n unlabeled nodes which are invariant when the two color classes are exchanged.

			Triangle begins:
  1;
  1, 1;
  1, 1,  1;
  1, 1,  1,   1;
  1, 1,  2,   1,    1;
  1, 1,  2,   2,    1,    1;
  1, 1,  4,   5,    4,    1,    1;
  1, 1,  4,  12,   12,    4,    1,   1;
  1, 1,  7,  31,   66,   31,    7,   1,  1;
  1, 1,  8,  90,  433,  433,   90,   8,  1, 1;
  1, 1, 12, 285, 3442, 7937, 3442, 285, 12, 1, 1;
  ...
The T(2,1) = 1 matrix is:
  [1 0]
  [0 1]
.
The T(4,2)= 2 matrices are:
  [1 1 0 0]   [1 1 0 0]
  [1 1 0 0]   [1 0 1 0]
  [0 0 1 1]   [0 1 0 1]
  [0 0 1 1]   [0 0 1 1]

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

Columns k=0..4 are A000012, A000012, A002865, A000840, A000843.
Row sums are A333160.
Central coefficients are A333165.
Cf. A008327, A122082, A333157, A133687, A333161.

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

A333893 Array read by antidiagonals: T(n,k) is the number of unlabeled loopless multigraphs with n nodes of degree k or less.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 4, 5, 3, 1, 1, 1, 5, 8, 10, 3, 1, 1, 1, 6, 14, 26, 16, 4, 1, 1, 1, 7, 20, 61, 60, 29, 4, 1, 1, 1, 8, 30, 128, 243, 184, 45, 5, 1, 1, 1, 9, 40, 254, 800, 1228, 488, 75, 5, 1, 1, 1, 10, 55, 467, 2518, 7252, 6684, 1509, 115, 6, 1

Offset: 0

Andrew Howroyd, Apr 08 2020

T(n,k) is the number of non-isomorphic n X n nonnegative integer symmetric matrices with all row and column sums equal to k and isomorphism being up to simultaneous permutation of rows and columns. The case that allows independent permutations of rows and columns is covered by A333737.

Terms may be computed without generating each graph by enumerating the graphs by degree sequence using dynamic programming. A PARI program showing this technique for the labeled case is given in A188403. Burnside's lemma as applied in A192517 can be used to extend this method to the unlabeled case.

			Array begins:
==============================================
n\k | 0 1  2   3    4     5      6       7
----+-----------------------------------------
  0 | 1 1  1   1    1     1      1       1 ...
  1 | 1 1  1   1    1     1      1       1 ...
  2 | 1 2  3   4    5     6      7       8 ...
  3 | 1 2  5   8   14    20     30      40 ...
  4 | 1 3 10  26   61   128    254     467 ...
  5 | 1 3 16  60  243   800   2518    6999 ...
  6 | 1 4 29 184 1228  7252  38194  175369 ...
  7 | 1 4 45 488 6684 78063 772243 6254652 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..377 (antidiagonals 0..26)

Rows n=0..4 are A000012, A000012, A000027(n+1), A006918(n+1), A333897.
Columns k=0..5 are A000012, A008619, A000990, A333894, A333895, A333896.
Cf. A188403, A192517, A263293, A333161, A333330, A333737, A334546.

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.

A333162 Number of regular graphs on n unlabeled nodes with half-edges.

Original entry on oeis.org

1, 2, 4, 6, 11, 16, 38, 78, 304, 1672, 19630, 450154, 20198620, 1673850034, 252574719718, 69216356716672, 34559361669877526, 31561018687380681802, 52958472442027295300520, 163901411216705405946164728, 939523329928455089556983977702

Offset: 0

Andrew Howroyd, Mar 11 2020

nonn

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

Row sums of A333161.

Cf. A322698, A333159.

A333163 Number of cubic graphs on n unlabeled nodes with half-edges.

Original entry on oeis.org

1, 0, 0, 1, 3, 4, 12, 24, 70, 172, 525, 1530, 5078, 16994, 61456, 228898, 895910, 3617148, 15130833, 65084088, 287828488, 1304327221, 6050218591, 28675928883, 138730847262, 684300453848, 3438439910436, 17585597712632, 91479580896616, 483699938173293, 2598090378779507

Offset: 0

Andrew Howroyd, Mar 11 2020

nonn

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

a(n) is the number of simple graphs on n unlabeled nodes with every node having degree 2 or 3.

Column k=3 of A333161.

Cf. A005638, A110040, A186417.

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

A333159 Triangle read by rows: T(n,k) is the number of non-isomorphic n X n symmetric binary matrices with k ones in every row and column up to permutation of rows and columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A333893 Array read by antidiagonals: T(n,k) is the number of unlabeled loopless multigraphs with n nodes of degree k or less.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A333162 Number of regular graphs on n unlabeled nodes with half-edges.

Views

Author

Keywords

Comments

Crossrefs

A333163 Number of cubic graphs on n unlabeled nodes with half-edges.

Views

Author

Keywords

Comments

Crossrefs