Complexity of counting the number of Good-perfect matching in the 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$?

1 Answer

There is only one instance for each size n. Thus, the problem is clearly in P/poly, and cannot possibly be #P-complete unless the polynomial hierarchy collapses.

In fact, it is polynomial-time computable. You can compute the first few terms of the sequence, and find that it goes 2, 6, 24, 160 ... . You can then look at the online encyclopedia of integer sequences and find it. When you look at the page for this sequence, you find a polynomial-time formula for computing it.