What would be the closed-form expression defining number of all possible labelled connected bipartite graphs given $\mid X \mid = m, \mid Y \mid = n - m $?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The number of connected labeled bipartite graphs with bipartition $(X,Y)$ where $|X|=m$ and $|Y|=n$ is the coefficient of $x^my^n/m!\,n!$ in $$\log\biggl(\sum_{m,n=0}^\infty 2^{mn} \frac{x^m}{m!}\frac{y^n}{n!}\biggr).$$ They are sequence A123260 in the OEIS.
$\begingroup$
$\endgroup$
Found the answer in Labeled Bipartite Blocks by F. Harary and R. W. Robinson (http://cms.math.ca/cjm/v31/cjm1979v31.0060-0068.pdf , page 63, formula 11):
$$C(m, n) = 2^{nm} - \sum{* \binom{n - 1}{a - 1} \binom{m}{b} 2^{(n - a)(m - b)} C(a, b) }.$$
The asterisk on the summation indicates conditions $1 \leq a \leq n$, $0 \leq b \leq m$, and either $a < n$ or $b < m$. The initial conditions are $R(0, 1) = 1$ and $R(0, n) = 0$ for $n \ne 1$, and it is obvious that $R(m, n) = R(n, m)$.