A007139 -id:A007139 - cp's OEIS frontend

A028657 Triangle read by rows: T(n,k) = number of n-node graphs with k nodes in distinguished bipartite block, k = 0..n.

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 7, 4, 1, 1, 5, 13, 13, 5, 1, 1, 6, 22, 36, 22, 6, 1, 1, 7, 34, 87, 87, 34, 7, 1, 1, 8, 50, 190, 317, 190, 50, 8, 1, 1, 9, 70, 386, 1053, 1053, 386, 70, 9, 1, 1, 10, 95, 734, 3250, 5624, 3250, 734, 95, 10, 1, 1, 11, 125, 1324, 9343, 28576, 28576, 9343, 1324, 125, 11, 1

Offset: 0

Vladeta Jovovic, Jun 16 2000

Also, row n gives the number of unlabeled bicolored graphs having k nodes of one color and n-k nodes of the other color; the color classes are not interchangeable.
Also the number of principal transversal matroids (also known as fundamental transversal matroids) of size n and rank k (originally enumerated by Brylawski). - Gordon F. Royle, Oct 30 2007
This sequence is also obtained if we read the array A(m,n) = number of inequivalent m X n binary matrices by antidiagonals, where equivalence means permutations of rows or columns (m>=0, n>=0) [Kerber]. - N. J. A. Sloane, Sep 01 2013

			The triangle T(n,k) begins:
  1;
  1,  1;
  1,  2,  1;
  1,  3,  3,  1;
  1,  4,  7,  4,  1;
  1,  5, 13, 13,  5,  1;
  1,  6, 22, 36, 22,  6,  1;
  ...
For example, there are 36 graphs on 6 nodes with a distinguished bipartite block with 3 nodes.
The array A(m,n) (m>=0, n>=0) (see Comments) begins:
  1 1  1    1     1      1        1         1           1 ...
  1 2  3    4     5      6        7         8           9 ...
  1 3  7   13    22     34       50        70          95 ...
  1 4 13   36    87    190      386       734        1324 ...
  1 5 22   87   317   1053     3250      9343       25207 ...
  1 6 34  190  1053   5624    28576    136758      613894 ...
  1 7 50  386  3250  28576   251610   2141733    17256831 ...
  1 8 70  734  9343 136758  2141733  33642660   508147108 ...
  1 9 95 1324 25207 613894 17256831 508147108 14685630688 ...
... - _N. J. A. Sloane_, Sep 01 2013

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

Alois P. Heinz, Rows n = 0..45, flattened (first 20 rows from R. W. Robinson)
Thomas H. Brylawski, An affine representation for transversal geometries, Studies in Appl. Math. 54 (1975), no. 2, 143-160.
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. See Table 1.
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] See Table 1.
M. A. Harrison, On the number of classes of binary matrices, IEEE Trans. Computers, 22 (1973), 1048-1051.
Vladeta Jovovic, Binary matrices up to row and column permutations
A. Kerber, Experimentelle Mathematik, Séminaire Lotharingien de Combinatoire. Institut de Recherche Math. Avancée, Université Louis Pasteur, Strasbourg, Actes 19 (1988), 77-83. [Annotated scanned copy]
B. Misek, On the number of classes of strongly equivalent incidence matrices, (Czech with English summary) Casopis Pest. Mat. 89 1964 211-218.
Carlos Simpson, Learning proofs for the classification of nilpotent semigroups, arXiv:2106.03015 [cs.LG], 2021.
Index to OEIS entries related to number of inequivalent matrices modulo permutation of row and columns.

Row sums give A049312.
A246106 is a very similar array.
Cf. A055080, A049312, A052265, A242093.
Diagonals of the array A(m,n) give A002724, A002725, A002728.
Rows (or columns) give A002623, A002727, A006148, A052264.
A(n,k) = A353585(2, n, k).

b:= proc(n, i) option remember; `if`(n=0, {0}, `if`(i<1, {},
      {seq(map(p-> p+j*x^i, b(n-i*j, i-1) )[], j=0..n/i)}))
    end:
g:= proc(n, k) option remember; add(add(2^add(add(igcd(i, j)*
      coeff(s, x, i)* coeff(t, x, j), j=1..degree(t)),
      i=1..degree(s))/mul(i^coeff(s, x, i)*coeff(s, x, i)!,
      i=1..degree(s))/mul(i^coeff(t, x, i)*coeff(t, x, i)!,
      i=1..degree(t)), t=b(n+k$2)), s=b(n$2))
    end:
A:= (n, k)-> g(min(n, k), abs(n-k)):
seq(seq(A(n, d-n), n=0..d), d=0..14); # Alois P. Heinz, Aug 01 2014

b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i<1, {}, Union[ Flatten[ Table[ Function[ {p}, p + j*x^i] /@ b[n - i*j, i-1], {j, 0, n/i}]]]]];
g[n_, k_] := g[n, k] = Sum[ Sum[ 2^Sum[ Sum[GCD[i, j] * Coefficient[s, x, i] * Coefficient[t, x, j], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}] / Product[i^Coefficient[s, x, i] * Coefficient[s, x, i]!, {i, 1, Exponent[s, x]}] / Product[i^Coefficient[t, x, i] * Coefficient[t, x, i]!, {i, 1, Exponent[t, x]}], {t, b[n+k, n+k]}], {s, b[n, n]}];
A[n_, k_] := g[Min[n, k], Abs[n-k]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Jan 28 2015, after Alois P. Heinz *)

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}
K(q, t)={sum(j=1, #q, gcd(t, q[j]))}
A(n, m)={my(s=0); forpart(q=m, s+=permcount(q)*polcoef(exp(sum(t=1, n, 2^K(q, t)/t*x^t) + O(x*x^n)), n)); s/m!}
{ for(r=0, 10, for(k=0, r, print1(A(r-k,k), ", ")); print) } \\ Andrew Howroyd, Mar 25 2020

\\ G(k,x) gives k-th column as rational function (see Jovovic link).
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}
Fix(q,x)={my(v=divisors(lcm(Vec(q))), u=apply(t->2^sum(j=1, #q, gcd(t, q[j])), v)); 1/prod(i=1, #v, my(t=v[i]); (1-x^t)^(sum(j=1, i, my(d=t/v[j]); if(!frac(d), moebius(d)*u[j]))/t))}
G(m,x)={my(s=0); forpart(q=m, s+=permcount(q)*Fix(q,x)); s/m!}
T(n,k)={my(m=max(k, n-k)); polcoef(G(n-m, x + O(x*x^m)), m)} \\ Andrew Howroyd, Mar 26 2020

A028657(n,k)=A353585(2, n, k) \\ M. F. Hasler, May 01 2022

A(m,n) = Sum_{p in P(m), q in P(n)} 2^Sum_{i in p, j in q} gcd(i,j) / (N(p) N(q)) where P(m) are the partition of m (see e.g., A036036), N(p) = Product_{distinct parts x in p} x^m(x)*m(x)!, m(x) = multiplicity of x in p. [corrected by Anders Kaseorg, Oct 04 2024]

A122082 Number of unlabeled bicolored graphs on 2n nodes which are invariant when the two color classes are interchanged.

Original entry on oeis.org

1, 2, 5, 16, 67, 404, 3904, 64840, 1930842, 104698904, 10401039400, 1900637187280, 641429385018832, 401454435464761376, 467919402404052870944, 1019758699013228238271040, 4171161230867751509749228304

Offset: 0

N. J. A. Sloane, Oct 18 2006

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 0..50
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]

Row sums of A123548.

Cf. A002724, A007139, A333160.

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]
a[n_] := (s=0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 06 2018, after Andrew Howroyd *)

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) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, (v[i]+1)\2)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 23 2017

a(n) = 2*A007139(n) - A002724(n). - Vladeta Jovovic, Feb 27 2007

More terms from Vladeta Jovovic, Feb 27 2007

A056152 Triangular array giving number of bipartite graphs with n vertices, no isolated vertices and a distinguished bipartite block with k=1..n-1 vertices, up to isomorphism.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 5, 5, 1, 1, 8, 17, 8, 1, 1, 11, 42, 42, 11, 1, 1, 15, 91, 179, 91, 15, 1, 1, 19, 180, 633, 633, 180, 19, 1, 1, 24, 328, 2001, 3835, 2001, 328, 24, 1, 1, 29, 565, 5745, 20755, 20755, 5745, 565, 29, 1, 1, 35, 930, 15274, 102089, 200082, 102089

Offset: 2

Vladeta Jovovic, Jul 29 2000

Also table read by rows: for 0 < k < n, a(n, k) = number of bipartite graphs with n vertices, no isolated vertices and a distinguished bipartite block with k vertices, up to isomorphism.
a(n, k) is the number of isomorphism classes of finite subdirectly irreducible almost distributive lattices in which the N-quotient has k upper covers and (n - k) lower covers. - David Wasserman, Feb 11 2002
Also, row n gives the number of unlabeled bicolored graphs having k nodes of one color and n-k nodes of the other color, with no isolated nodes; the color classes are not interchangeable.

			Triangle begins:
  1;
  1,  1;
  1,  3,   1;
  1,  5,   5,   1;
  1,  8,  17,   8,  1;
  1, 11,  42,  42,  11,  1;
  1, 15,  91, 179,  91,  15,  1;
  1, 19, 180, 633, 633, 180, 19, 1;
  ...
There are 17 bipartite graphs with 6 vertices, no isolated vertices and a distinguished bipartite block with 3 vertices, or equivalently, there are 17 3 X 3 binary matrices with no zero rows or columns, up to row and column permutation:
[0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1] [0 0 1]
[0 0 1] [0 0 1] [0 1 0] [0 1 0] [0 1 0] [0 1 1] [0 1 1] [0 1 1] [1 1 0]
[1 1 0] [1 1 1] [1 0 0] [1 0 1] [1 1 1] [1 0 1] [1 1 0] [1 1 1] [1 1 0]
and
[0 0 1] [0 0 1] [0 1 1] [0 1 1] [0 1 1] [0 1 1] [0 1 1] [1 1 1]
[1 1 0] [1 1 1] [0 1 1] [0 1 1] [1 0 1] [1 0 1] [1 1 1] [1 1 1]
[1 1 1] [1 1 1] [1 0 1] [1 1 1] [1 1 0] [1 1 1] [1 1 1] [1 1 1].

J. G. Lee, Almost Distributive Lattice Varieties, Algebra Universalis, 21 (1985), 280-304.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

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. See Table 2.
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] See Table 2.

Columns k=1..6 are A000012, A024206, A055609, A055082, A055083, A055084.
Row sums give A055192.
See A122083 for another version of this triangle.
Cf. A049312, A048194, A028657, A049311.

A007140 Number of unlabeled bicolored graphs, with no isolated nodes, on 2n nodes having n nodes of each color and allowing the color classes to be interchanged.

Original entry on oeis.org

1, 1, 3, 14, 115, 2086, 101791, 14835870, 6852422567, 10338780759514, 51804974736769271, 872530598196790164797, 49930445153769776449253479, 9805619466642079028742952893709, 6670375074613812276139335045628924297, 15853216549413764390038207575938343994222273

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

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]

Row sums of A123547.

Cf. A007139, A054976, A319155.

a(n) = (A054976(n) + A319155(n)) / 2. - Andrew Howroyd, Sep 25 2018

a(11)-a(15) from Andrew Howroyd, Sep 25 2018

A055082 Number of 4 X n binary matrices with no zero rows or columns, up to row and column permutation.

Original entry on oeis.org

1, 8, 42, 179, 633, 2001, 5745, 15274, 38000, 89331, 199715, 427184, 878152, 1741964, 3345562, 6239390, 11327863, 20065972, 34747460, 58924066, 98002370, 160086580, 257148244, 406637336, 633669040, 973971441, 1477810227, 2215179768, 3282598034, 4811946882

Offset: 1

Vladeta Jovovic, Jun 13 2000

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..1000
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]

Column k=4 of A056152.

Cf. A024206, A055609, A054976, A048291.

Vec((G(4, x) - G(3, x))*(1 - x) + O(x^30)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

Terms a(21) and beyond from Andrew Howroyd, Mar 25 2020

A122083 Triangle read by rows in which row n gives the number of unlabeled bicolored graphs having k nodes of one color and n-k nodes of the other color, with no isolated nodes; the color classes are not interchangeable.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 3, 1, 0, 0, 1, 5, 5, 1, 0, 0, 1, 8, 17, 8, 1, 0, 0, 1, 11, 42, 42, 11, 1, 0, 0, 1, 15, 91, 179, 91, 15, 1, 0, 0, 1, 19, 180, 633, 633, 180, 19, 1, 0, 0, 1, 24, 328, 2001, 3835, 2001, 328, 24, 1, 0, 0, 1, 29, 565, 5745, 20755, 20755

Offset: 0

N. J. A. Sloane, Oct 19 2006

			K M N Gives the number N of unlabeled bicolored graphs with no isolated nodes and having K nodes of one color and M nodes of the other color.
0 0 1
Total( 0)= 1
0 1 0
1 0 0
Total( 1)= 0
0 2 0
1 1 1
2 0 0
Total( 2)= 1
0 3 0
1 2 1
2 1 1
3 0 0
Total( 3)= 2
0 4 0
1 3 1
2 2 3
3 1 1
4 0 0
Total( 4)= 5
0 5 0
1 4 1
2 3 5
3 2 5
4 1 1
5 0 0
Total( 5)= 12
0 6 0
1 5 1
2 4 8
3 3 17
4 2 8
5 1 1
6 0 0
Total( 6)= 35

J. G. Lee, Almost Distributive Lattice Varieties, Algebra Universalis, 21 (1985), 280-304.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

R. W. Robinson, First 20 rows, flattened
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. See Table 2.
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] See Table 2.

Row sums give A055192. See A056152 for a version of this triangle with the bounding zeros in each row.

A123547 Triangle read by rows: T(n,k) = number of unlabeled bicolored graphs with no isolated nodes having 2n nodes and k edges, with n nodes of each color. Here n >= 0, 0 <= k <= n^2.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 2, 4, 3, 2, 1, 1, 0, 0, 0, 0, 1, 2, 8, 14, 21, 20, 20, 12, 9, 4, 2, 1, 1, 0, 0, 0, 0, 0, 1, 2, 10, 31, 76, 137, 221, 285, 321, 301, 253, 182, 122, 69, 38, 19, 10, 4, 2, 1, 1, 0, 0, 0, 0, 0, 0, 1, 2, 11, 43, 162, 451, 1121, 2314, 4255, 6702

Offset: 0

N. J. A. Sloane, Nov 14 2006

The colors may be interchanged.

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

R. W. Robinson, Rows 0 through 7, flattened
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]

Row sums give A007140. Cf. A007139, A106498 (gives beginning of this triangle).

A106498 Triangle read by rows: T(n,k) = number of unlabeled bicolored graphs with isolated nodes allowed having 2n nodes and k edges, with n nodes of each color. Here n >= 0, 0 <= k <= n^2.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 4, 5, 5, 4, 2, 1, 1, 1, 1, 2, 4, 10, 13, 23, 26, 32, 26, 23, 13, 10, 4, 2, 1, 1, 1, 1, 2, 4, 10, 20, 39, 72, 128, 198, 280, 353, 399, 399, 353, 280, 198, 128, 72, 39, 20, 10, 4, 2, 1, 1, 1, 1, 2, 4, 10, 20, 50, 99, 227, 458, 934, 1711

Offset: 0

N. J. A. Sloane, Nov 14 2006

The colors may be interchanged.

			Triangles A106498 and A123547 begin:
n = 0
k = 0 : 1, 1
Total = 1, 1
n = 1
k = 0 : 1, 0
k = 1 : 1, 1
Total = 2, 1
n = 2
k = 0 : 1, 0
k = 1 : 1, 0
k = 2 : 2, 1
k = 3 : 1, 1
k = 4 : 1, 1
Totals = 6, 3
n = 3
k = 0 : 1, 0
k = 1 : 1, 0
k = 2 : 2, 0
k = 3 : 4, 1
k = 4 : 5, 2
k = 5 : 5, 4
k = 6 : 4, 3
k = 7 : 2, 2
k = 8 : 1, 1
k = 9 : 1, 1
Totals = 26, 14

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

R. W. Robinson, Rows 0 through 7, flattened
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]

Row sums give A007139. Cf. A007140, A123547.

cp's OEIS Frontend

A028657 Triangle read by rows: T(n,k) = number of n-node graphs with k nodes in distinguished bipartite block, k = 0..n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

A122082 Number of unlabeled bicolored graphs on 2n nodes which are invariant when the two color classes are interchanged.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A056152 Triangular array giving number of bipartite graphs with n vertices, no isolated vertices and a distinguished bipartite block with k=1..n-1 vertices, up to isomorphism.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A007140 Number of unlabeled bicolored graphs, with no isolated nodes, on 2n nodes having n nodes of each color and allowing the color classes to be interchanged.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A055082 Number of 4 X n binary matrices with no zero rows or columns, up to row and column permutation.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

A122083 Triangle read by rows in which row n gives the number of unlabeled bicolored graphs having k nodes of one color and n-k nodes of the other color, with no isolated nodes; the color classes are not interchangeable.

Views

Author

Keywords

Examples

References

Links

Crossrefs

A123547 Triangle read by rows: T(n,k) = number of unlabeled bicolored graphs with no isolated nodes having 2n nodes and k edges, with n nodes of each color. Here n >= 0, 0 <= k <= n^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A106498 Triangle read by rows: T(n,k) = number of unlabeled bicolored graphs with isolated nodes allowed having 2n nodes and k edges, with n nodes of each color. Here n >= 0, 0 <= k <= n^2.

Views

Author

Keywords

Comments

Examples

References

Links