A005333 Number of 2-colored connected labeled graphs with n vertices of the first color and n vertices of the second color.

1, 5, 205, 36317, 23679901, 56294206205, 502757743028605, 17309316971673776957, 2333508400614646874734621, 1243000239291173897659593056765, 2629967962392578020413552363565293565, 22170252073745058975210005804934596601690557

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Conjecture: if n > 1, then a(n) is the number of labeled digraphs D (allowing self-loops) with n vertices such that D|D' and D'|D are (strongly) connected (see preliminaries of Broere et al.). - Lorenzo Sauras Altuzarra, Sep 17 2022

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..50
• I. Broere, W. Imrich, R. Kalinowski, and M. Pilsniak, Asymmetric colorings of products of graphs and digraphs, Discrete Applied Mathematics 266 (p. 56-64), 2019.
• F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
• F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)

Crossrefs

Main diagonal of A262307 and A227322.

Programs

Mathematica

c[0, 1] = c[1, 0] = 1; c[0, ] = c[, 0] = 0; c[n_, m_] := c[n, m] = 2^(n*m) - Sum[If[k < n || j < m, Binomial[n - 1, k - 1]*Binomial[m, j]* 2^((n - k)*(m - j))*c[k, j], 0], {k, 1, n}, {j, 0, m}];
a[n_] := c[n, n];
Array[a, 12] (* Jean-François Alcover, Sep 03 2019 *)

Formula

a(n) = c(n,n) where c(0,1) = 1, c(0,m) = 0, c(n,m) = 2^(n*m) - Sum_{1 <= k <= n, 0 <= j <= m, k < n or j < m} C(n-1, k-1) * C(m, j) * 2^((n-k)*(m-j)) * c(k, j). - Sean A. Irvine, May 11 2016

Extensions

More precise definition by Pavel Irzhavski, Jul 09 2013

More terms from Sean A. Irvine, May 11 2016