number of permutations of $[2n]$ that move exactly k elements from $\{1,...,n\}$ to $\{n+1,...,2n\}$ I'm trying to figure out the size of
$S^{(k)}:=\{\sigma\in S_{2n}\ :\ \sigma \text{ moves exactly }k\text{ elements from }\{1,\dots,n\} \text{ to }\{n+1,\dots,2n\}\}$ for $k=0,\dots,n$, where $S_d$ is the permutation group of $[n]$.
$|S^{(0)}|=(n!)^2$ because we there $n!$ permutations in each half and any (directed, in the sense $(\sigma_1,\sigma_2)\in S_n\times S_n$) pair is a valid.
For $k>0$ I got the formula $|S^{(k)}|=\big(\prod\limits_{j=0}^{k-1}(n-j)^2\big)((n-k)!)^2$
The way I explain it is: first we choose the elements that change halves (meaning they go from $[n]$ to $\{n+1,\dots,2n\}$ or the other way around). Note that for each $i\in[n]$ that switches there is a $\bar i\in\{n+1,\dots,2n\}$ that switches. There are $n$ options for the first one that goes from $[n]$ to $\{n+1,\dots,2n\}$, call it  $i_1$, and $n$ options for where it is mapped. And there are $n$ options for a corresponding element $\bar i_1$ from $\{n+1,\dots,n\}$ that will be mapped to $[n]$. For the second one there are $n-1$ options for the element $i_2$ from $[n]\backslash \{i_1\}$ and $n-1$ for where it goes, because it is mapped to $\{n+1,\dots,2n\}\backslash\{\sigma(i_1)\}$.
And similarly for the corresponding element that goes from $\{n+1,\dots,2n\}\backslash\{\bar i_1\}$ to $[n]\backslash \{\sigma(\bar i_1)\}$. And we continue like this $k$ times in total.
Then for the elements that stay in their respective halves we have to choose permutations of $[n-k]$ and $[n-k]+n$ hence the formula.
But it doesn't seem to be true according to mathematica...
Can you spot the obvious error?
 A: You're overcounting the options that can go from the first half to the second half — for instance, you're counting the permutation $(1 3)(2 4)\in S_4$ once by choosing $1$ as your first element and $2$ as your second, and then again by choosing $2$ as your first element and $1$ as your second. Instead, you can think of choosing a subset of $[1\ldots n]$ and a subset of $[n+1\ldots 2n]$ of the same size, and then considering all of the possible mappings between those two subsets.
A: The count should be
$$
\frac{n!^4}{k!^2(n-k)!^2}\ .
$$
To do the count properly draw two copies of the big set of $2n$ elements and represent a permutation by arrows going from the first copy to the second.
Then you first pick who in the bottom half of the 1st copy goes to the other half. That gives a factor $\binom{n}{k}$. Then chose how precisely you connect them to destinations in the top half of the the second copy. That gives a factor $n!/(n-k)!$. You do the same for the $k$ elements in the top half of the first copy which must go to the bottom half of the second copy. So you get another factor $\binom{n}{k}\times\frac{n!}{(n-k)!}$.
Now you connect the remaining $n-k$ departure points in the bottom half of the first copy. The spots available to them are the $n-k$ remaining destination points in the bottom half of the second copy. So you have $(n-k)!$ possibilities. Finally, you connect the remaining $n-k$ departure points in the top half of the first copy. So here comes another $(n-k)!$.
So altogether the count is
$$
\binom{n}{k}\times\frac{n!}{(n-k)!}
\times
\binom{n}{k}\times\frac{n!}{(n-k)!}
\times (n-k)!^2
$$
which simplifies to I formula I have given above.
The count can also be done probabilistically and rephrased as an urn problem.
That's because the probability of picking such a permutation among $(2n)!$ possible is the expression
$$
\frac{\binom{n}{k}\ \binom{n}{n-k}}{\binom{2n}{n}}
$$
which appears in the Chu-Vandermonde identity and related to the hypergeometric probability distribution.
