Number of ways to hook up all vertices of a bipartite graph? Let A represent the number of labeled vertices on the left side of a bipartite graph, and let B represent the number of labeled vertices on the right. How many ways are there to connect every vertex in A to some number of vertices in B such that no vertex in B is left behind?
You are only given A and B, the number of labeled vertices in the left and right set. I am asking how many ways there are to place edges such that no vertex is left untouched.
Edit: For some reason I can't reply to the messages below, so I have to do it here. I don't think the current answers are right. By exhaustion I count 7 such cases for A=B=2, whereas the answers return 9.
Edit again: Look at the upper left and lower left graphs of the pictures posted below in Fabrício Caluza Machad's answer. Some vertices don't have any edges connecting to them. This is what I mean by "no vertex untouched."
 A: Use the inclusion-exclusion principle. 
Let $|A|=n, |B|=m$.
There are $2^{nm}$ bipartite graphs between $A$ and $B$. From these, $\binom{m}{k}2^{n(m-k)}$ reach at most $m-k$ vertices from $B$. by The inclusion exclusion principle, the number you seek is
$$\sum_{k=0}^m (-1)^k \binom{m}{k}2^{n(m-k)} =2^{mn}\sum_{k=0}^m  \binom{m}{k}(\frac{-1}{2^{n}})^k =2^{mn}(1-\frac{1}{2^{n}})^m=(2^n-1)^m$$
Edit:
*Second solution*
The answer suggested the following simpler solution:
Any such graph is uniquely determined by the set of vertices connected with every vertex of $B$.
Let $X$ denote the set of all non-empty subsets of $A$ and let 
You can uniquely identify any graph $G$ like in the problem with a function $f: B \to X$ by
$$f(v)  :=\{ u \in A | uv \in E(G) \} \,.$$
Moreover, any $f: B \to X$ uniquely determines a bipartite graph like in the problem, with $V(G)=A \cup B$ and 
$$E(G)= \{ uv| v \in B, u \in f(v) \} \,.$$
It is easy to prove that the processes I described define inverse functions, thus the number of graphs is equal with the number of function $f: B \to X$, which is 
$$|X|^{|B|}=(2^{|A|}-1)^{|B|}$$

ADDED AFTER THE CLARIFICATION
To solve the same  problem for $A$, do again the same process for $A$. There are $(2^n-1)^m$. 
The number of such graphs which don't use $k$ particular fixed vertices are 
$$(2^{n-k}-1)^m$$
Thus bi inclusion Exclusion principle, the total number is:
$$\sum_{k=0}^n (-1)^k \binom{n}{k}(2^{n-k}-1)^m$$
A: You can solve it with the inclusion-exclusion principle.
Let $\mathcal  B_i, 1 \leq i \leq |B|$ be the family of graphs such that $b_i \in B$ isn't connected with a vertice in $A$. We can count the number of graphs in $\mathcal B_i$ as $2^{|A|\ (|B|-1)} $ (every vertex in $A$ can connect with $|B|-1$ vertices in $B$)
Similarly, if $I \subset \{1,2,...,|B|\}$ and $i = |I|$, then $| \bigcap_{k\in I} \mathcal B_k| = 2^{|A|\ (|B|-i)} $.
So, what you want to count is:
$|( \bigcup_{k=1}^{|B|} \mathcal B_k)^C | = 2^{|A||B|} - \sum_{k=1}^{|B|}(-1)^{k-1}\binom{|B|}{k}2^{|A|\ (|B|-k)} = \sum_{k=0}^{|B|}(-1)^{k}\binom{|B|}{k}2^{|A|\ (|B|-k)}$
Answering question edit: case |A| = 2 and |B| = 2, we have 9 answers:

