Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let's $G=(U, V, E)$ be a balanced bipartite graph which $|U|=|V|=n$ and $|E|=n*(n-1)$; All nodes in $U$ are connected to all nodes in $V$ except $u_i$ to $v_i$ for $1\leq i \leq n$.

Definition1: Cross edges are two edges in $E$, one with two end points $u_i$, $v_j$ and the other with $u_j$, $v_i$.
Definition2: Good-perfect matching is a perfect matching with no cross edges.

What is the complexity of counting the number of Good-perfect matching in $G$?

share|cite|improve this question
Looks like you are looking for number of permutations without fixed points (1-cycles) and without (2-cycles). I doubt you can do better than Ross' answer of linear time. – Aryabhata Jan 5 '11 at 22:35
@Moron: when I got the expression for P(n) right, it matches A038205 which has the description you give. – Ross Millikan Jan 6 '11 at 0:50
up vote 4 down vote accepted

I believe it is linear. Define P(n) as the number of good-perfect matchings on n points. We have to match $u_1$ to something, n-1 choices, and it might as well be $v_2$. Now we are not allowed to connect $u_2$ to $v_1$, so let C(n) be the number of ways of completing a good-perfect matching on n points with one set of mismatched indices that cannot be connected. Similarly let D(n) be the number of ways of completing a good-perfect matching with one set of mismatched indices that are allowed to be matched. After we connect $u_2$ to $v_3$ we are allowed to connect $u_3$ to $v_1$, so we have a case of D.

The recurrences are $$P(n)=(n-1)C(n-1)$$ $$C(n)=(n-1)D(n-1)$$ $$D(n)=P(n-1)+(n-1)D(n-1)$$ started with $D(1)=1, C(1)=0, P(1)=0$ which leads to


This is A038205 in OEIS, which does not list a closed form solution. Note: I corrected an error in the expression for P(n) and the numbers in the table.

share|cite|improve this answer
The probability that a permutation has no cycles of length 3 or less appears to be $e^{-3/2}$, and in fact empirically the expression $n! e^{-3/2}$ seems to get roughly half the digits of $P(n)$ correct. (In the case of derangements, the expression $n! e^{-1}$ gets essentially all of the digits correct.) – Peter Shor Jan 7 '11 at 20:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.