cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 11 results. Next

A133687 Triangle with number of equivalence classes of n X n matrices over {0,1} with rows and columns summing to k (0<=k<=n), where equivalence is defined by row and column permutations.

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, 7, 4, 1, 1, 1, 1, 4, 16, 16, 4, 1, 1, 1, 1, 7, 51, 194, 51, 7, 1, 1, 1, 1, 8, 224, 3529, 3529, 224, 8, 1, 1, 1, 1, 12, 1165, 121790, 601055, 121790, 1165, 12, 1, 1, 1, 1, 14, 7454, 5582612, 156473848, 156473848, 5582612, 7454, 14, 1, 1
Offset: 0

Views

Author

Joost Vermeij (joost_vermeij(AT)live.nl), Jan 04 2008

Keywords

Comments

T(n,k) = T(n,n-k). When 0 and 1 are switched, the number of equivalence classes remain the same.
Terms may be computed without generating each matrix by enumerating the number of matrices by column sum sequence using dynamic programming. A PARI program showing this technique for the labeled case is given in A008300. Burnside's lemma can be used to extend this method to the unlabeled case. This seems to require looping over partitions for both rows and columns. The number of partitions squared increases rapidly with n. For example, A000041(20)^2 = 393129. - Andrew Howroyd, Apr 03 2020

Examples

			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,   7,    4,    1,   1;
  1, 1, 4,  16,   16,    4,   1, 1;
  1, 1, 7,  51,  194,   51,   7, 1, 1;
  1, 1, 8, 224, 3529, 3529, 224, 8, 1, 1;
  ...

Links

Crossrefs

Columns k=0..5 are A000012, A000012, A002865, A000512, A000513, A000516.
Row sums are A333681.
T(2n,n) gives A333740.
Cf. A000519, A008300 (labeled case), A008327 (bipartite graphs), A333159 (symmetric case).

Formula

Sum_{k=1..n} T(n, k) = A000519(n).

Extensions

Missing a(72) inserted by Andrew Howroyd, Apr 01 2020

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.

Original entry on oeis.org

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

Views

Author

Andrew Howroyd, Mar 09 2020

Keywords

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.

Examples

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

Links

Crossrefs

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.

Programs

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

Formula

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

A333737 Array read by antidiagonals: 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 up to permutations 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, 3, 1, 1, 1, 1, 3, 5, 5, 1, 1, 1, 1, 3, 9, 12, 7, 1, 1, 1, 1, 4, 13, 33, 29, 11, 1, 1, 1, 1, 4, 20, 74, 142, 79, 15, 1, 1, 1, 1, 5, 28, 163, 556, 742, 225, 22, 1, 1, 1, 1, 5, 39, 319, 1919, 5369, 4454, 677, 30, 1, 1
Offset: 0

Views

Author

Andrew Howroyd, Apr 08 2020

Keywords

Comments

Terms may be computed without generating each matrix by enumerating the number of matrices by column sum sequence using dynamic programming. A PARI program showing this technique for the labeled case is given in A188403. Burnside's lemma as applied in A318805 can be used to extend this method to the unlabeled case.

Examples

			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 1  2   2    3     3      4       4 ...
  3 | 1 1  3   5    9    13     20      28 ...
  4 | 1 1  5  12   33    74    163     319 ...
  5 | 1 1  7  29  142   556   1919    5793 ...
  6 | 1 1 11  79  742  5369  31781  156191 ...
  7 | 1 1 15 225 4454 64000 692599 5882230 ...
  ...
The T(3,3) = 5 matrices are:
   [0 0 3]  [0 1 2]  [0 1 2]  [1 0 2]  [1 1 1]
   [0 3 0]  [1 1 1]  [1 2 0]  [0 3 0]  [1 1 1]
   [3 0 0]  [2 1 0]  [2 0 1]  [2 0 1]  [1 1 1]

Links

Crossrefs

Rows n=0..5 are A000012, A000012, A008619, A106607, A333886, A333887.
Columns n=0..5 are A000012, A000012, A000041, A333888, A333889, A333890.
Main diagonal is A333738.
Cf. A188403 (labeled case), A333159 (binary), A333733 (not necessarily symmetric).
Cf. A318805, A333893.

A008327 Triangle read by rows: T(n,k) is the number of simple regular bipartite graphs with 2n nodes and degree k, (0 <= k <= n).

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, 6, 4, 1, 1, 1, 1, 4, 14, 14, 4, 1, 1, 1, 1, 7, 41, 130, 41, 7, 1, 1, 1, 1, 8, 157, 1981, 1981, 157, 8, 1, 1, 1, 1, 12, 725, 62616, 304496, 62616, 725, 12, 1, 1, 1, 1, 14, 4196, 2806508, 78322916
Offset: 0

Views

Author

Brendan McKay

Keywords

Comments

This sequence can be derived from A008326 by Euler transform. - Andrew Howroyd, Apr 03 2020

Examples

			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,   6,    4,    1,   1;
  1, 1, 4,  14,   14,    4,   1, 1;
  1, 1, 7,  41,  130,   41,   7, 1, 1;
  1, 1, 8, 157, 1981, 1981, 157, 8, 1, 1;
  ...

Links

Crossrefs

Column k=0..5 are A000012, A000012, A002865, A008325, A333730, A333731.
Row sums are A008324.
Cf. A051031, A008326, A087114, A133687, A333159.

Formula

Column k is the Euler transform of column k of A008326. - Andrew Howroyd, Apr 03 2020

Extensions

More terms from Eric Rogoyski, May 15 1997
Name clarified by Andrew Howroyd, Sep 05 2018

A008326 Triangle read by rows: T(n,k) is the number of simple regular connected bipartite graphs with 2n nodes and degree k, (2 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 5, 4, 1, 1, 1, 13, 14, 4, 1, 1, 1, 38, 129, 41, 7, 1, 1, 1, 149, 1980, 1981, 157, 8, 1, 1, 1, 703, 62611, 304495, 62616, 725, 12, 1, 1, 1, 4132, 2806490, 78322915, 78322916, 2806508, 4196, 14, 1, 1, 1, 29579, 158937213, 27033154060, 147252447227, 27033154065, 158937367, 29817, 21, 1, 1
Offset: 2

Views

Author

Brendan McKay and Eric Rogoyski

Keywords

Comments

This sequence can be derived from A133687 and A333159. In particular, if w(n) is the inverse Euler transform of column k of A133687 and s(n) is the inverse Euler transform of column k of A333159, then 2*T(2*n+1,k) = w(2*n+1) + s(2*n+1) and 2*T(2*n,k) = w(2*n) + s(2*n) - w(n) + T(n,k). - Andrew Howroyd, Apr 03 2020

Examples

			Triangle begins:
  1;
  1,   1;
  1,   1,    1;
  1,   2,    1,    1;
  1,   5,    4,    1,   1;
  1,  13,   14,    4,   1, 1;
  1,  38,  129,   41,   7, 1, 1;
  1, 149, 1980, 1981, 157, 8, 1, 1;
  ...

Links

Crossrefs

Columns k=3..7 are A006823, A006824, A006825, A014385, A014387.
Row sums are in A008323.
Cf. A008327, A133687, A333159.

Extensions

More terms from Eric Rogoyski, May 15 1997
Name clarified by Andrew Howroyd, Sep 05 2018
Terms a(55) and beyond from Andrew Howroyd, Apr 03 2020

A333161 Triangle read by rows: T(n,k) is the number of k-regular graphs on n unlabeled nodes with half-edges.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 3, 3, 3, 1, 1, 3, 4, 4, 3, 1, 1, 4, 8, 12, 8, 4, 1, 1, 4, 10, 24, 24, 10, 4, 1, 1, 5, 17, 70, 118, 70, 17, 5, 1, 1, 5, 24, 172, 634, 634, 172, 24, 5, 1, 1, 6, 36, 525, 4428, 9638, 4428, 525, 36, 6, 1, 1, 6, 50, 1530, 35500, 187990, 187990, 35500, 1530, 50, 6, 1
Offset: 0

Views

Author

Andrew Howroyd, Mar 11 2020

Keywords

Comments

A half-edge is like a loop except it only adds 1 to the degree of its vertex.
T(n,k) is the number of non-isomorphic n X n symmetric binary matrices with k ones in every row and column and isomorphism being up to simultaneous permutation of rows and columns. The case that allows independent permutations of rows and columns is covered by A333159.
T(n,k) is the number of simple graphs on n unlabeled vertices with every vertex degree being either k or k-1.

Examples

			Triangle begins:
  1;
  1, 1;
  1, 2,  1;
  1, 2,  2,   1;
  1, 3,  3,   3,    1;
  1, 3,  4,   4,    3,    1;
  1, 4,  8,  12,    8,    4,    1;
  1, 4, 10,  24,   24,   10,    4,   1;
  1, 5, 17,  70,  118,   70,   17,   5,  1;
  1, 5, 24, 172,  634,  634,  172,  24,  5, 1;
  1, 6, 36, 525, 4428, 9638, 4428, 525, 36, 6, 1;
  ...
The a(2,1) = 2 adjacency matrices are:
  [0 1]  [1 0]
  [1 0]  [0 1]
.
The A(4,2) = 3 adjacency matrices are:
  [0 0 1 1]   [1 1 0 0]   [1 1 0 0]
  [0 0 1 1]   [1 1 0 0]   [1 0 1 0]
  [1 1 0 0]   [0 0 1 1]   [0 1 0 1]
  [1 1 0 0]   [0 0 1 1]   [0 0 1 1]

Links

Crossrefs

Columns k=0..3 are A000012, A004526(n+2), A186417, A333163.
Row sums are A333162.
Central coefficients are A333166.
Cf. A051031, A333157, A333159.

Formula

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

A000840 Number of cubic bicolored graphs on n unlabeled nodes admitting an automorphism exchanging the colors.

Original entry on oeis.org

0, 0, 1, 1, 2, 5, 12, 31, 90, 285, 938, 3285, 11983, 45390, 177803, 718390, 2986407, 12749364, 55802982, 250068732, 1145923828, 5363795830, 25620207380, 124767647097, 618983876918, 3126035142910, 16060182735947, 83883575376862, 445164927249466, 2399098651337048
Offset: 1

Views

Author

Brendan McKay and Eric Rogoyski

Keywords

Crossrefs

Column k=3 of A333159.
Cf. A000512, A000843, A004066, A008325.

Extensions

a(11)-a(30) from Andrew Howroyd, Mar 10 2020

A333160 Number of non-isomorphic n X n symmetric binary matrices with an equal number of ones in every row and column up to permutation of rows and columns.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 17, 36, 146, 1066, 15419, 406684, 19284912, 1635874946, 249424764407, 68725494158824, 34418706513939926, 31487353344361957012, 52887877379630894268187, 163777247316556715401451972, 939121048579630147375554814224
Offset: 0

Views

Author

Andrew Howroyd, Mar 10 2020

Keywords

Comments

a(n) is the number of regular bicolored graphs on 2n unlabeled nodes which are invariant when the two color classes are interchanged.

Examples

			The a(2) = 3 matrices are:
  [0 0]  [1 0]  [1 1]
  [0 0]  [0 1]  [1 1]

Crossrefs

Row sums of A333159.
Cf. A122082, A322698, A333162.

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

Views

Author

Andrew Howroyd, Mar 11 2020

Keywords

Comments

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

Examples

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

Crossrefs

Central coefficients of A333159.
Cf. A333164, A333166.

Formula

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

A000843 Number of quartic bicolored graphs on n unlabeled nodes admitting an automorphism exchanging the colors.

Original entry on oeis.org

0, 0, 0, 1, 1, 4, 12, 66, 433, 3442, 30404, 294951, 3093770, 34846185, 419020738, 5355289843, 72466668921, 1034818990771, 15548633703424, 245182764121059, 4047990858838185, 69826392559499108, 1256005988628521464, 23517396850332614602, 457623646061902648705
Offset: 1

Views

Author

Brendan McKay and Eric Rogoyski

Keywords

Crossrefs

Column k=4 of A333159.
Cf. A000513, A000840.

Extensions

a(11)-a(25) from Andrew Howroyd, Mar 10 2020
Showing 1-10 of 11 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.