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.

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,5

Comments

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.

References

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.

Links

Table of n, a(n) for n=2..63.

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.

Example

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

Crossrefs

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.

Sequence in context: A296327 A347970 A296541 * A171229 A125690 A176481

Adjacent sequences: A056149 A056150 A056151 * A056153 A056154 A056155

Keyword

nonn,tabl

Author

Vladeta Jovovic, Jul 29 2000

Status

approved