Lower bound on counting perfect matchings in bipartite graph Let $G=(V_1 \cup V_2,E)$ be a finite bipartite graph. If every vertex in $V_1$ has degree at least $r\le|V_1|$ and $G$ has a perfect matching, we want to show there are at least $r!$ complete matchings from $V_1$.
I wanted to use the number of injections between two sets of $r$ elements but I cannot find out such sets...
By the way since $G$ has a perfect matching, we have $|V_1|=|V_2|$. Plus we can use Hall's theorem which claims that $\forall S \subset V_1,\,|N_G(S)|\geq |S| $, it is also right for $V_2$.
 A: Let $G$ be a finite bipartite graph with bipartition $V_1 \cup V_2$.  If $G$ has at least one perfect matching, and every vertex in $V_1$ has degree at least $r$, we are to prove a lower bound $r!$ on the number of perfect matchings.
A theorem of Phillip Hall (1935) gives the well-known necessary and sufficient "Hall's Condition" for a matching that covers $V_1$, already mentioned in the Question above.  For every subset $S \subseteq V_1$, let $N(S) \subseteq V_2$ be the set of nodes adjacent to some node in $S$.

Bipartite graph $G$ has a matching that covers finite $V_1$ if and only if
for every subset $S \subseteq V_1$, $|N(S)| \ge |S|$.

In 1948 Marshall Hall Jr. (no relation) published a refinement of Philip Hall's result which gives the desired lower bound on the number of different matchings that cover $V_1$:

If $r = \text{min}_{v \in V_1} \text{deg}(v)$, then there are at least
$\prod_{i=1}^{\text{min}\{r,|V_1|\}} (r+1-i)$ matchings covering $V_1$.

For the sake of completeness we will give a proof of this, but since we've stated matters in greater generality than required for the Question, let's begin by verifying that in our specific case the lower bound amounts to $r!$.  Since a perfect matching exists, $|V_1| = |V_2|$, and since $r \le |V_2|$, the upper limit of the product is simply $r=\text{min}\{r,|V_1|\}$, and:
$$\prod_{i=1}^r (r+1-i) = r\cdot (r-1)\ldots \cdot 1 = r! $$
The following proof is closely adapted from Thm. 2.1.5 of D.B. West's The Art of Combinatorics - Volume I. Extremal Graph Theory, Chapter 2: Matching and Independence.
The necessity of Hall's Condition is easy, since any matching that covers $V_1$ will cover any $S \subseteq V_1$, implying that $|N(S)| \ge |S|$.  The sufficiency will now be shown by proving the stated lower bound by induction on $m = |V_1|$.
For the basis step $m=1$ we have $r$ matchings, since that is the degree of the one vertex in $V_1$.
Now let $m \gt 1$.  Consider two cases:
Case 1:  Suppose a strict inequality throughout Hall's Condition, that is:
$$ |N(S)| \gt |S| \; \text{ for every nonempty proper subset } \; S \subset V_1 $$
For fixed node $u \in V_1$, choose any adjacent node $v \in V_2$.  This can be chosen in at least $r$ ways.  Whichever choice is made, $G - \{u,v\}$ still satisfies Hall's Condition because no subset of $V_1 - {u}$ has lost more than one neighbor, and we have the strict inequality above allowing for that loss.  Each node of $V_1 - {u}$ has degree at least $r-1$, so applying the induction hypothesis and multiplying by the factor $r$ just mentioned gives the desired lower bound in this case.
Case 2: On the other hand suppose there exists nonempty proper subset $S \subset V_1$ for which $|N(S)| = |S|$.  A matching that covers $V_1$ will necessarily amount to a matching on the restriction $G_1$ of $G$ to $S \cup N(S)$ and another matching on $G_2$ the restriction of $G$ to $G - (S \cup N(S))$.  Since $G_1$ contains all the neighbors of $S$, the minimum degree of $S$ nodes in $G_1$ is $r \le |N(S)| = |S|$. The induction hypothesis therefore applies to the number of matchings that cover $S$ in $G_1$ to give at least:
$$ \prod_{i=1}^r (r+1-i) $$
The induction hypothesis also applies to give at least one matching that covers $V_1 - S$ in $G_2$, since if there were a node $u \in (V_1 - S)$ that had neighbors only in $N(S)$, then $S' = S \cup \{u\}$ would be a subset of $V_1$ for which Hall's Condition fails.
It follows that the above product is also a lower bound on the number of matchings that cover $V_1$ in $G$. This completes the second case, and thus the proof by induction.
