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$?
 A: 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.
