For a random permutation, what's the probability that each half of the elements keep relative order? If we take a random permutation of  a sequence of $2k$ elements,  $X_1, X_2, \ldots X_k, X_{k+1}, \ldots, X_{2k}$.  What's the probability that $X_1, X_2, .. X_k$ and $X_{k+1}, \ldots, X_{2k}$ both keep their relative orders in the new sequence?
My guess is, these 2 event are independent because whether one happen doesn't change the other's probability.  So we have
$$
\Pr \{ [\text {both sub-sequence keep relative order}]\} = (\frac 1 {n!})^2
$$
What do you think about it?  Is it possible to get the result by counting how many permutations fulfill the condition?

Your reasoning seems correct to me. Another way of getting it: 
To count the posible arrangements, lets imagine the first $k$ elements are white and the rest black. It's easy to see if we are given the colors of a particular arrangement, the elements can be identified; hence, to count all "legal" permutations is equivalent to count all the possible ways of placing $k$ black and $k$ white elements in $2k$ positions. This is ${2n  \choose n}$. And the total number of permutations is $(2n)!$ 
Hence, the probability is
$$\frac{{2n  \choose n}}{(2n)!} = \frac{1}{(n!)^2}$$
