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?

  • 4
    $\begingroup$ This problem is essentially counting derangements, permutations with no fixed points. $\endgroup$ – Jair Taylor Feb 20 '14 at 20:29
  • $\begingroup$ Please post it as an answer. $\endgroup$ – Mohammad Al-Turkistany Feb 21 '14 at 10:32
  • $\begingroup$ Okay, I've answered it below. $\endgroup$ – Jair Taylor Feb 21 '14 at 16:22

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!}$.

  • $\begingroup$ Thank you. This is exactly the type of answer that I was looking for. BTW, Are you aware of any asymptomatic lower-bound? $\endgroup$ – Mohammad Al-Turkistany Feb 21 '14 at 16:54
  • $\begingroup$ 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$. $\endgroup$ – Jair Taylor Feb 21 '14 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.