Assume that we have a bipartite graph called $G$ such that $G=(X, Y)$ and we have $X=\{x_1,\dots,x_n\}$ and $Y=\{y_1,\dots,y_n\}$.
For each $1\leq i\leq n$, $x_i$ is adjacent to $\{y_1,\dots,y_n\}$ \ $\{y_i\}$. What is the number of perfect matchings in this graph?
I personally thought that maybe we can solve it recursively, and I have just compute for small $n$’s like 3 and 4. I got 2 for $n=3$ and 9 for $n=4$.
I will work out the case $n=4$ with the in-and-out formula. I think you will see how to generalize it.
Let $H$ be the complete bipartite graph with vertex sets $\{x_1,x_2,x_3,x_4\}$ and $\{y_1,y_2,y_3,y_4\}$. It has all $16$ edges $x_iy_j$ and $4!=24$ perfect matchings, but we only want to count the perfect matchings that don't use any of the edges $x_iy_i$.
Let $E$ be the set of all $24$ perfect matchings in $H$, and let $A_i$ be the set of perfect matchings that use the edge $x_iy_i$. The set we want to count is $E\setminus(A_1\cup A_2\cup A_3\cup A_4)$. By the in-and-out formula, $$|E\setminus(A_1\cup A_2\cup A_3\cup A_4)|$$ $$=|E|-|A_1|-|A_2|-|A_3|-|A_4|$$ $$+|A_1\cap A_2|+|A_1\cap A_3|+|A_1\cap A_4|+|A_2\cap A_3|+|A_2\cap A_4|+|A_3\cap A_4|$$ $$-|A_1\cap A_2\cap A_3|-|A_1\cap A_2\cap A_4|-|A_1\cap A_3\cap A_4|-|A_2\cap A_3\cap A_4|$$ $$+|A_1\cap A_2\cap A_3\cap A_4|.$$ Now $|E|=4!$ and $|A_1|=3!$ and $|A_1\cap A_2|=2!$ and $|A_1\cap A_2\cap A_3|=1!$ and $|A_1\cap A_2\cap A_3\cap A_4|=0!$, so the mess above evaluates to $$\binom404!-\binom413!+\binom422!-\binom431!+\binom440!$$ $$=\frac{4!}{0!}-\frac{4!}{1!}+\frac{4!}{2!}-\frac{4!}{3!}+\frac{4!}{4!}$$ $$=24-24+12-4+1=\boxed{9}.$$ Can you take it from here? For $n=5$ you should get $$\frac{5!}{0!}-\frac{5!}{1!}+\frac{5!}{2!}-\frac{5!}{3!}+\frac{5!}{4!}-\frac{5!}{5!}$$ $$=120-120+60-20+5-1=\boxed{44}.$$ If you don't like the way I did it, just look up derangements on Wikipedia or something.