Let $G$ be a simple bipartite graph with left part $L(G)$ and right part $R(G)$. For $S \subseteq L(G)$, denote $N(S)$ the set of neighbours of vertices of $S$. Define the surplus $s(G)$ as $\min_{S \subseteq L(G), S \neq \varnothing} |N(S)| - |S|$. Hall's lemma says that $G$ has a matching covering $L(G)$ iff $s(G) \geq 0$. Further, any $G$ with $s(G) \leq 0$ has a matching of size $|L(G)| + s(G)$ (most easily shown by the "18th camel" trick).
Let $M(G)$ be the number of matchings in $G$ covering $L(G)$. Let $m(n, d)$ be the smallest $M(G)$ among graphs $G$ with $|L(G)| = n$ and $s(G) \geq d$. For example, $m(n, 0) = 1$: lower bound is Hall's lemma, and the upper bound is reached on the $n$-edge matching graph.
We can borrow a natural upper bound for $m(n, d)$ from the "18th camel" argument: take an $n$-edge matching graph, and add $d$ extra vertices to the right part connected with every vertex on the left. For the resulting graph $G_{n, d}$ we have $m(n, d) \leq M(G_{n, d}) = \sum_{k = 0}^d {d \choose k} (n)_k$. This bound is obviously tight for $d = 0$, and further tight for $d = 1$ as $m(n, 1) \geq n + 1$ by Proposition 7 of this paper. In general, this construction seems very efficient at minimizing $M(G)$, but it is not obvious if/why it is best possible.
Question: is $m(n, d) = M(G_{n, d})$ for all positive $n$ and $d$?
