A008327 -id:A008327 - cp's OEIS frontend

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.

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

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

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

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

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

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

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

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

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

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

Brendan McKay and Eric Rogoyski

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

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

Andrew Howroyd, Table of n, a(n) for n = 2..154
B. D. McKay and E. Rogoyski, Latin squares of order ten, Electron. J. Combinatorics, 2 (1995) #N3.

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

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

A008325 Number of simple regular trivalent bipartite graphs with 2n nodes.

Original entry on oeis.org

1, 1, 2, 6, 14, 41, 157, 725, 4196, 29816, 246644, 2297075, 23503477, 260265023, 3090336300, 39101547971, 524782945991, 7443247863498, 111221983956652, 1746165682538497, 28734206614035245, 494526496354065244, 8883865784392246280, 166286434745252091055, 3237719048384605059117, 65477287940472122129194

Offset: 3

Brendan McKay

Euler transform of A006823. - Peter J. Taylor, Sep 28 2017

G. Brinkmann, Fast generation of cubic graphs, Journal of Graph Theory, 23(2):139-149, 1996.
Sean A. Irvine, On the difference between A004066 and A008325

Column k=3 of A008327.

Cf. A004066 (bicolored), A006823 (connected).

A006823 = Cases[Import["https://oeis.org/A006823/b006823.txt", "Table"], {, }][[All, 2]];
etr[f_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d f[d], {d, Divisors[j]}] b[n - j], {j, 1, n}]/n]; b];
b[n_] := If[n >= 3, A006823[[n - 2]], 0];
a = etr[b];
a /@ Range[3, 16] (* Jean-François Alcover, Dec 03 2019 *)

a(15)-a(16) from Peter J. Taylor, Sep 28 2017

Terms a(17) and beyond from Andrew Howroyd, Apr 03 2020

A008324 Number of simple regular bipartite graphs with 2n nodes.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 18, 40, 230, 4296, 431206, 162267272, 201636689771, 777816803942186, 9865957936943931964, 395886667549681689591841, 53716176608076643470621234239, 23524515269630339982914646821899537, 35682168849414944013547274452501768506834

Offset: 0

Brendan McKay

First differs from A333732 at n = 12. - Andrew Howroyd, Apr 03 2020

Brendan McKay and E. Rogoyski, Latin squares of order ten, Electron. J. Combinatorics, 2 (1995) #N3.

Row sums of A008327.

Cf. A033995, A008323, A333732.

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

A333730 Number of simple 4-regular bipartite graphs with 2n nodes.

Original entry on oeis.org

0, 0, 0, 1, 1, 4, 14, 130, 1981, 62616, 2806508, 158937367, 10773254138, 855658147832, 78558952717569, 8251166899386729, 982806390786806618, 131756175056777580011, 19748565975966429686408, 3289970442222058710279611, 605948437043760750748781907, 122796504004669690100342096563

Offset: 1

Andrew Howroyd, Apr 03 2020

nonn

Column k=4 of A008327.

Euler transform of A006824.

A333731 Number of simple 5-regular bipartite graphs with 2n nodes.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 4, 41, 1981, 304496, 78322916, 27033154065, 11934777413049, 6593485023089912, 4485517185017734885, 3707462300996644966161, 3680029088808704302571244, 4341813441626431900011624077, 6033239205199253768404631967656, 9792722283774379198364367866020815

Offset: 1

Andrew Howroyd, Apr 03 2020

nonn

Column k=5 of A008327.

Euler transform of A006825.

A087114 Number of regular bipartite simple graphs on n nodes.

Original entry on oeis.org

1, 1, 2, 1, 3, 1, 4, 1, 6, 1, 8, 1, 18, 1, 40, 1, 230, 1, 4296, 1, 431206, 1, 162267272, 1, 201636689771, 1, 777816803942186, 1, 9865957936943931964, 1, 395886667549681689591841, 1, 53716176608076643470621234239, 1, 23524515269630339982914646821899537, 1, 35682168849414944013547274452501768506834, 1

Offset: 0

Eric W. Weisstein, Aug 13 2003

nonn

A graph must be regular and bipartite to be a semisymmetric graph.

Eric Weisstein's World of Mathematics, Semisymmetric Graph

Cf. A008323, A008324, A008327.

a(2*n + 1) = 1, a(2*n) = A008324(n). - Andrew Howroyd, Sep 05 2018

a(10)-a(19) from Andrew Howroyd, Sep 05 2018

a(0)=1 prepended and a(20) onwards added by Andrew Howroyd, Feb 21 2024

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A008325 Number of simple regular trivalent bipartite graphs with 2n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A008324 Number of simple regular bipartite graphs with 2n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A333730 Number of simple 4-regular bipartite graphs with 2n nodes.

Views

Author

Keywords

Crossrefs

Formula

A333731 Number of simple 5-regular bipartite graphs with 2n nodes.

Views

Author

Keywords

Crossrefs

Formula

A087114 Number of regular bipartite simple graphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions