login
Number of 2-colored connected labeled graphs with n vertices of the first color and n vertices of the second color.
(Formerly M4030)
14

%I M4030 #40 Oct 25 2022 20:30:12

%S 1,5,205,36317,23679901,56294206205,502757743028605,

%T 17309316971673776957,2333508400614646874734621,

%U 1243000239291173897659593056765,2629967962392578020413552363565293565,22170252073745058975210005804934596601690557

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

%C 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

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

%H Andrew Howroyd, <a href="/A005333/b005333.txt">Table of n, a(n) for n = 1..50</a>

%H I. Broere, W. Imrich, R. Kalinowski, and M. Pilsniak, <a href="http://home.agh.edu.pl/~pilsniak/34.pdf">Asymmetric colorings of products of graphs and digraphs</a>, Discrete Applied Mathematics 266 (p. 56-64), 2019.

%H F. Harary and R. W. Robinson, <a href="http://dx.doi.org/10.4153/CJM-1979-007-3">Labeled bipartite blocks</a>, Canad. J. Math., 31 (1979), 60-68.

%H F. Harary and R. W. Robinson, <a href="/A001832/a001832.pdf">Labeled bipartite blocks</a>, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)

%F 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

%t 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}];

%t a[n_] := c[n, n];

%t Array[a, 12] (* _Jean-François Alcover_, Sep 03 2019 *)

%Y Main diagonal of A262307 and A227322.

%K nonn

%O 1,2

%A _N. J. A. Sloane_

%E More precise definition by _Pavel Irzhavski_, Jul 09 2013

%E More terms from _Sean A. Irvine_, May 11 2016