# Counting restricted perfect matchings

It is known that counting perfect matchings in bipartite graphs is $\#P$-hard.

Given a complete bipartite graph $G(U \cup V, E)$, where $|U|=|V|=n$ and a perfect matching $M \subset E$, what is the number of perfect matchings $N$ such that $M \cap N= \phi$?

I want to count such restricted matching as a function of $n$.

Is there a known formula? If not, what is the best asymptotic lower-bound on the number of restricted matchings?

• This problem is essentially counting derangements, permutations with no fixed points. – Jair Taylor Feb 20 '14 at 20:29
The matchings on the complete bipartite graph you describe are essentially permutations. Let $U = \{u_1, \ldots, u_n\}, V = \{v_1, \ldots, v_n\}$. Given a complete matching on G, define a permutation $\sigma: \{1,2,\ldots,n\} \rightarrow \{1,2,\ldots,n\}$ by $\sigma(i) = j$ when $u_i$ is matched to $v_j$. It doesn't matter which matching $M$ is, so after reordering we can assume that $u_i$ is matched to $v_i$ for $i = 1, \ldots, n$. Then the matchings $N$ that are disjoint from $M$ correspond exactly to derangements: Permutations $\sigma$ with no fixed points, that is, $\sigma(i) \neq i$ for each $i$. There is a well-known formula for the number of derangements $D(n)$ of $\{1, 2, \ldots, n\}$ that can be found with the inclusion-exclusion formula: $D(n) = \sum_{i=0}^n (-1)^i \frac{n!}{i!}$.
• From the Taylor series expansion of $1/e$ we can see that $D(n) \approx n!/e$. In fact, $D(n)$ is the closest integer to $n!/e$. – Jair Taylor Feb 21 '14 at 17:24