# Complexity of counting the number of Good-perfect matching in bipartite graph

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$?

• 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

## 1 Answer

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

$\begin{array}{rrrr}n&D&C&P\\1&1&0&0\\2&1&1&0\\3&2&2&2\\4&8&6&6\\5&38&32&24\\6&214&190&160\\7&1444&1284&1140\\8&11248&10108&8988\\9&98972&89984&80864\\10&971612&890748&809856\end{array}$

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.

• 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