4
$\begingroup$

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

  • 1
    @Moron: when I got the expression for P(n) right, it matches A038205 which has the description you give.2011-01-06

1 Answers 1

4

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.

  • 1
    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.)2011-01-07