A122082 -id:A122082 - cp's OEIS frontend

A318869 Inverse Euler transform of A122082.

1, 2, 2, 8, 37, 270, 3049, 56576, 1795917, 100752972, 10189362127, 1879720761478, 637617233746767, 400169631649617320, 467115844246535037894, 1018822456144129013291710, 4169121243929999971120036590, 32126195519194538602120203293590

Offset: 0

Andrew Howroyd, Sep 04 2018

nonn

This sequence is an intermediate step in the computation of A005142 and A123549.

The combinatoric interpretation is that of connected bicolored graphs on 2n nodes which are invariant when the two color classes are interchanged plus pairs of identical connected bicolored graphs on n nodes each which are not invariant when the two color classes are interchanged. The former is A123549(n) and the later is A005142(n) for odd n and A005142(n) - A123549(n/2) for even n.

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

Cf. A005142, A122082, A123549, A318870.

mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
permcount[v_] := Module[{m=1, s=0, k=0, t}, For[i=1, i <= Length[v], i++, t = v[[i]]; k = If[i>1 && t == v[[i-1]], k+1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i-1}] + Total @ Quotient[v+1, 2]
b[n_] := (s=0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Join[{1}, EULERi[Array[b, 20]]] (* Jean-François Alcover, Sep 13 2018, after Andrew Howroyd *)

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

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

A007139 Number of unlabeled bicolored bipartite graphs on 2n nodes having n nodes of each color with no edges between vertices of the same color and allowing the color classes to be interchanged.

Original entry on oeis.org

1, 2, 6, 26, 192, 3014, 127757, 16853750, 7343780765, 10733574184956, 52867617324773592, 882178116079222400788, 50227997322550920824045262, 9837048598740665027344331562224, 6681839615514161556535851222043192179, 15867777966020615016665849049841756464001994

Offset: 0

N. J. A. Sloane

nonn

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Marko Riedel, Table of n, a(n) for n = 0..30
F. Harary, L. March and R. W. Robinson, On enumerating certain design problems in terms of bicolored graphs with no isolates, Environment and Planning, B 5 (1978), 31-43.
F. Harary, L. March and R. W. Robinson, On enumerating certain design problems in terms of bicolored graphs with no isolates, Environment and Planning B: Urban Analytics and City Science, 5 (1978), 31-43. [Annotated scanned copy]
Marko Riedel, Cycle indices for K_{n,n} including shuffles and reflections.
Marko Riedel, Maple code for cycle indices of K_{n,n}

Cf. A007140.

a(n) = (A002724(n)+A122082(n))/2. - Vladeta Jovovic, Feb 27 2007

More terms from Vladeta Jovovic, Feb 27 2007
Edited by N. J. A. Sloane, Aug 14 2007
Name clarified by Marko Riedel, Jun 15 2017
More terms from Marko Riedel, Jun 16 2017

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

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

Andrew Howroyd, Mar 10 2020

nonn

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

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

Row sums of A333159.

Cf. A122082, A322698, A333162.

A123548 Triangle read by rows: T(n,k) = number of unlabeled bicolored graphs having 2n nodes and k edges, which are invariant when the two color classes are interchanged. Here n >= 0, 0 <= k <= n^2.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 2, 1, 1, 1, 1, 1, 1, 2, 4, 5, 7, 8, 9, 8, 7, 5, 4, 2, 1, 1, 1, 1, 1, 1, 2, 4, 6, 9, 14, 22, 29, 33, 37, 43, 43, 37, 33, 29, 22, 14, 9, 6, 4, 2, 1, 1, 1, 1, 1, 1, 2, 4, 6, 10, 16, 29, 46, 69, 99, 141, 183, 230, 277, 319, 342, 352, 342, 319, 277, 230, 183, 141, 99, 69, 46, 29, 16, 10, 6, 4, 2, 1, 1, 1

Offset: 0

N. J. A. Sloane, Nov 14 2006

			Triangle begins:
n = 0
k = 0 : 1
************************ total ( 2n = 0) = 1
n = 1
k = 0 : 1
k = 1 : 1
************************ total ( 2n = 2) = 2
n = 2
k = 0 : 1
k = 1 : 1
k = 2 : 1
k = 3 : 1
k = 4 : 1
************************ total ( 2n = 4) = 5
n = 3
k = 0 : 1
k = 1 : 1
k = 2 : 1
k = 3 : 2
k = 4 : 3
k = 5 : 3
k = 6 : 2
k = 7 : 1
k = 8 : 1
k = 9 : 1
************************ total ( 2n = 6) = 16

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1978.

Andrew Howroyd, Rows n=0..20, flattened (rows 0..7 from R. W. Robinson)

Row sums give A122082.

Cf. A008406.

permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v, t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i], v[j])); t(2*v[i]*v[j]/g)^g )) * prod(i=1, #v, my(c=v[i]); t(2*c)^(c\2)*if(c%2, t(c), 1))}
Row(n) = {my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i)); Vecrev(s/n!)}
{ for(n=0, 6, print(Row(n))) } \\ Andrew Howroyd, Mar 08 2020

A319155 Number of bicolored graphs on 2n unlabeled nodes without isolated nodes and which are invariant when the two color classes are interchanged.

Original entry on oeis.org

1, 1, 3, 11, 51, 337, 3500, 60936, 1866002, 102768062, 10296340496, 1890236147880, 639528747831552, 400813006079742544, 467517947968588109568, 1019290779610824185400096, 4170141472168738281510957264, 32130367702064742239376997422512

Offset: 0

Andrew Howroyd, Sep 25 2018

nonn

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

Cf. A007140, A122082.

permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total @ Quotient[v + 1, 2];
A122082[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
a[n_] := A122082[n] - A122082[n-1];
a /@ Range[0, 17] (* Jean-François Alcover, Sep 05 2019, after Andrew Howroyd in A122082 *)

a(n) = A122082(n) - A122082(n-1).

cp's OEIS Frontend

A318869 Inverse Euler transform of A122082.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

A007139 Number of unlabeled bicolored bipartite graphs on 2n nodes having n nodes of each color with no edges between vertices of the same color and allowing the color classes to be interchanged.

Views

Author

Keywords

References

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

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

A123548 Triangle read by rows: T(n,k) = number of unlabeled bicolored graphs having 2n nodes and k edges, which are invariant when the two color classes are interchanged. Here n >= 0, 0 <= k <= n^2.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

A319155 Number of bicolored graphs on 2n unlabeled nodes without isolated nodes and which are invariant when the two color classes are interchanged.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula