2
$\begingroup$

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 $?

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.