What would be the closedform expression defining number of all possible labelled connected bipartite graphs given $\mid X \mid = m, \mid Y \mid = n  m $?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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. 


Found the answer in Labeled Bipartite Blocks by F. Harary and R. W. Robinson (http://cms.math.ca/cjm/v31/cjm1979v31.00600068.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)$. 

