Question: Let $\mathfrak{S}_{2n}$ be the permutations on $[2n]=\{1,2,\ldots, 2n\}$. Let $$\mathcal{J}_n=\{\sigma\in \mathfrak{S}_{2n} \mid \sigma(i) \not\equiv \sigma(i+n)\mod n, \text{ for all $i\in [n]$}\}.$$
Prove that $$|\mathcal{J}_n|=\sum_{k=0}^n\frac{(-2)^k(n!)^2(2n-2k)!}{k!(n-k)!}.$$
Approach: I believe that this problem can be solved with rook polynomials. The issue I am having is that in all the examples I've seen, the restrictions for the permutations are of the form $\sigma(i)\neq j$. In such cases, determining the board for which to compute the rook polynomial on is straightforward. However, in this problem the restrictions are relative i.e. of the form $\sigma(i)\not\equiv \sigma(i+n)\bmod n$ and so I'm not sure what the correct board is going to be? I would naively think that the board should be $2n\times 2n$, and we place the restrictions on $(i,i+n\bmod n)$ but the summation in the final formula seems to suggest an $n\times n$ board. Any advice or alternate approaches would be appreciated, perhaps i'm missing a straightforward exponential generating function approach.
Second Approach: As mentioned in the comments, the relative positions perhaps make the rook polynomial approach ineffective, as suggested inclusion/exclusion should be the right tool. With this in mind we remark that we can suggestively rewrite the solution as $$|\mathcal{J}_n|=\sum_{k=0}^n (-1)^k\binom{n}{k}\left(2^kn!(2(n-k))!\right),$$ and interpreting $2^kn!(2(n-k))!$ as the number of permutations with at least some set of properties then the answer would be the number of permutation with none of the properties… would the $i$th property be $\sigma(i)\equiv \sigma(i+n)\mod n$?
Best Answer
There appears to be a missing exponent in the denominator: the $(n-k)!$ ought to be squared.
For $k\in[n]$ let $A_k$ be the set of permutations $\sigma$ such that $\sigma(k)\equiv\sigma(k+n)\pmod n$. There are $2n$ choices for $\langle\sigma(k),\sigma(k+n)\rangle$ and $(2n-2)!$ permutations of the remaining $2n-2$ members of $[2n]$, so $|A_k|=2n(2n-2)!$. If $\varnothing\ne I\subseteq[n]$, and $|I|=k$, then
$$\left|\bigcap_{i\in I}A_i\right|=2^k\frac{n!}{(n-k)!}(2n-2k)!\;,$$
so
$$\begin{align*} \left|\bigcup_{k=1}^nA_k\right|&=\sum_{\varnothing\ne I\subseteq[n]}(-1)^{|I|+1}\left|\bigcap_{k\in I}A_k\right|\\ &=\sum_{k=1}^n(-1)^{k+1}2^k\binom{n}k\frac{n!}{(n-k)!}(2n-2k)!\\ &=\sum_{k=1}^n(-1)^{k+1}2^k\frac{n!^2(2n-2k)!}{k!(n-k)!^2}\;, \end{align*}$$
and the number of good permutations is
$$\begin{align*} (2n)!-\sum_{k=1}^n(-1)^{k+1}2^k\frac{n!^2(2n-2k)!}{k!(n-k)!^2}&=(2n)!+\sum_{k=1}^n(-1)^k2^k\frac{n!^2(2n-2k)!}{k!(n-k)!^2}\\ &=\sum_{k=0}^n(-1)^k2^k\frac{n!^2(2n-2k)!}{k!(n-k)!^2}\\ &=\sum_{k=0}^n\frac{(-2)^kn!^2(2n-2k)!}{k!(n-k)!^2}\;. \end{align*}$$