Counting Bipartite Graphs! I am given two sets of vertices such that the first set contains $n$ vertices labeled $1$ to $n$ and the second set contains $m$ vertices labeled $1$ to $m$.
I am required to add edges between these vertices such that no two vertices from the same set are adjacent and each vertex is incident on at least one edge. 
I need to find the number of graphs that can be formed under the above constraints.
I thought a lot on finding some type of recurrence relation in terms of $n$, $m$, but couldn't come up with the solution. Help me please.
 A: Think to the biadjacency matrix: the problem is equivalent to enumerate the number of $n \times m$ binary matrices with no zero rows or columns. Then use the Inclusion-Exclusion principle:
$$\sum_{k=1}^m(-1)^{m-k}\binom{m}{k}(2^k-1)^n$$
where at the step $k$, given $S$, one of the $\binom{m}{k}$ $k$-subsets of the columns $w_1,w_2,\dots,w_m$, we choose for each row $v_1,\dots,v_n$, one of the $(2^k-1)$ non-zero binary $m$-tuples with ones in $S$.
A: Let $V = \{v_i\}_{1\leq i \leq n}$ and $W = \{w_j\}_{1\leq j \leq m}$ be sets of $n$ and $m$ vertices corresponding to each part. I will write $[\![s]\!]$ to refer to $\{1,\dots ,s\}$. Essentially, we can characterize each bipartite graph $G$ with a function
$$
\Gamma_G : [\![n]\!] \longrightarrow \mathcal{P}([\![m]\!]) \setminus \{\emptyset\}
$$
such that $\Gamma_G(i) = \{j : w_j \in N(v_i)\}$. Note that from this we can also recover $N(w_j)$ for $w_j \in W$. Therefore, our problem reduces to counting the amount functions from $[\![n]\!]$ to $\mathcal{P'} := \mathcal{P}([\![m]\!]) \setminus \{\emptyset\}$ such that every vertex in $W$ has a neighbour, that is, $\cup_{i \in [\![n]\!]} \Gamma(i) = [\![m]\!]$. I will denote this set as
$$
\mathcal{F} = \{\Gamma \in (\mathcal{P}')^{[\![n]\!]} :  \cup_{i \in [\![n]\!]} \Gamma(i) = [\![m]\!]\}
$$
Since there are $(2^m -1)^n$ functions of the form $f : [\![n]\!] \to \mathcal{P}'$ in total, it would suffice to count $\mathcal{F}^c$ and substract it from $(2^m -1)^n$. Now, because
$$
\mathcal{F}^c = \bigcup_{j \in [\![m]\!]}\{\Gamma \in (\mathcal{P}')^{[\![n]\!]} :  j \not \in \Gamma(i) \  (\forall i \in [\![n]\!])\}
$$
we can count this set using the inclusion-exclusion principle:
$$
|\mathcal{F}^c| = \sum_{k = 1}^m(-1)^{k+1}\sum_{\emptyset \subsetneq S \subseteq [\![m]\!], |S| = k}|\bigcap_{s \in S}\{\Gamma \in (\mathcal{P}')^{[\![n]\!]} :  s \not \in \Gamma(i) \  (\forall i \in [\![n]\!])\}|
$$
More concisely,
$$
|\mathcal{F}^c| = \sum_{k = 1}^m(-1)^{k+1}\sum_{\emptyset \subsetneq S \subseteq [\![m]\!], |S| = k}|\{\Gamma \in (\mathcal{P}')^{[\![n]\!]} :  S \cap \Gamma(i) = \emptyset \  (\forall i \in [\![n]\!])\}|
$$
Let's count each set of the inner sum. If $S$ is a proper subset of $[\![m]\!]$, to give a function such that each image is disjoint with $S$ is the same as giving a function that maps each $i \in [\![n]\!]$ to a subset of $[\![m]\!] \setminus S$ (except the empty set which we have already excluded). Therefore, for each $i \in [\![n]\!]$ we have $2^{m-|S|}-1$ choices, giving a total of $(2^{m-|S|}-1)^n$. Thus,
$$
|\mathcal{F}^c| = \sum_{k = 1}^m(-1)^{k+1}\sum_{\emptyset \subsetneq S \subseteq [\![m]\!], |S| = k}(2^{m-|S|}-1)^n = \sum_{k = 1}^m(-1)^{k+1}{m\choose k}(2^{m-k}-1)^n 
$$
And finally,
$$
|\mathcal{F}| = |(\mathcal{P})^{[\![n]\!]} \setminus \mathcal{F}^c| = |(\mathcal{P})^{[\![n]\!]}| - |\mathcal{F}^c| =  (2^m -1)^n - |\mathcal{F}^c| = \\=(2^m -1)^n + \sum_{k = 1}^m{m\choose k}(-1)^k(2^{m-k}-1)^n = \\
= \sum_{k = 0}^m{m\choose k}(-1)^k(2^{m-k}-1)^n = \sum_{k = 1}^m{m\choose k}(-1)^{m-k}(2^{k}-1)^n.
$$
