A055084 -id:A055084 - cp's OEIS frontend

A055192 Number of bipartite graphs with n vertices, no isolated vertices and a distinguished bipartite block, up to isomorphism.

1, 2, 5, 12, 35, 108, 393, 1666, 8543, 54190, 436740, 4565450, 62930604, 1156277748, 28509174012, 946786816168, 42448800498744, 2573207315483554, 211180300735118954, 23490473719472829824, 3545759835559406756008, 727077827560669587718290

Offset: 2

Vladeta Jovovic, Jun 18 2000

nonn

Also the number of connected split graphs on n vertices (cf. A048194). - Falk Hüffner, Dec 01 2015

Inverse Euler transform is A007776. - Andrew Howroyd, Oct 03 2018

Alois P. Heinz, Table of n, a(n) for n = 2..40

Equals second differences of A049312.
Cf. A007776, A024206, A055609, A055082, A055083, A055084.
Row sums of A056152 and also of A122083.

b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Flatten @ Table[ Map[ 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]];
A049312[d_] := Sum[A[n, d - n], {n, 0, d}];
Differences[Table[A049312[n], {n, 0, 23}], 2] (* Jean-François Alcover, Sep 05 2019, after Alois P. Heinz in A049312 *)

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.

A121231 Number of n X n binary matrices M (that is, real matrices with entries 0 and 1) such that M^2 is also a binary matrix.

Original entry on oeis.org

1, 2, 11, 172, 6327, 474286, 67147431, 17080038508

Offset: 0

Dan Dima, Aug 21 2006

Comments from Brendan McKay, Aug 21 2006: Equivalently, directed graphs (simple but loops allowed) without a few small forbidden subgraphs (those allowing 2 distinct paths of length 2 from vertex x to vertex y for some x,y; I think there are 6 possibilities). One can also consider isomorphism classes of those digraphs.
Comment from  Rob Pratt, Aug 03 2008: A121294 provides a lower bound on the maximum number of 1's in such a matrix M. There are cases where a higher number is reached; the following 5 X 5 matrix has 11 ones and its square is binary:
0 0 1 0 0
0 0 0 0 1
1 1 0 0 1
1 1 0 1 0
1 1 0 1 0.
The optimal values seem to match A070214, verified for n <= 7.
Term (5,1) of the n-th power of the 5 X 5 matrix shown is A001045(n), the Jacobsthal sequence. - Gary W. Adamson, Oct 03 2008
a(n) >= A226321(n).

Eric Weisstein's World of Mathematics, Background information about adjacency matrices
E. W. Weisstein, (0,1)-Matrix, MathWorld. [P. Petsie, Aug 03 2008]
Wikipedia, Background information about adjacency matrices
Index entries for matrices, binary, which are squares

Cf. A226321, A225371, A055084, A052264, A051589, A069452, A053304, A001045, A121294, A070214.

Edited by R. J. Mathar, Oct 01 2008
a(7) from R. H. Hardin, Jun 19 2012. This makes it clear that the old A122527 was really a badly-described version of this sequence, and that a(7) was earlier found by Balakrishnan (bvarada2(AT)jhu.edu), Sep 17 2006. - N. J. A. Sloane, Jun 19 2012
Entry revised by N. J. A. Sloane, Jun 19 2012

A005747 Number of n-covers of an unlabeled 6-set.

Original entry on oeis.org

1, 16, 196, 2197, 22952, 223034, 2004975, 16642937, 127654604, 907349654, 6000728764, 37093282121, 215296646264, 1178514299094, 6108871834312, 30098215339608, 141433252447082, 635816643771438, 2742163498527536, 11374522802412498, 45482770393453638

Offset: 1

N. J. A. Sloane, Simon Plouffe

nonn

Number of n X 6 binary matrices with at least one 1 in every column up to row and column permutations. - Andrew Howroyd, Feb 28 2023

R. J. Clarke, Covering a set by subsets, Discrete Math., 81 (1990), 147-152.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Vladeta Jovovic, Binary matrices up to row and column permutations

A diagonal of A055080.

First differences give A055084.

Vec((G(6, x) - G(5, x)) + O(x^30)) \\ G defined in A028657. - Andrew Howroyd, Feb 28 2023

Corrected and extended by Vladeta Jovovic, Jun 13 2000

Terms a(20) and beyond from Andrew Howroyd, Feb 28 2023

cp's OEIS Frontend

A055192 Number of bipartite graphs with n vertices, no isolated vertices and a distinguished bipartite block, up to isomorphism.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

A121231 Number of n X n binary matrices M (that is, real matrices with entries 0 and 1) such that M^2 is also a binary matrix.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A005747 Number of n-covers of an unlabeled 6-set.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions