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?

The independence argument looks sound to me, although the assumptions might need justification depending on who you ask. You simply take the indices of the first $k$ objects after permutation and rank them; this effects a permutation of the $k$ objects and by symmetry there is no preference for one permutation over another. Only one permutation preserves the relative ordering (the identity) so the probability they keep their ordering is $1/k!$. The fulfillment of this condition is independent between the first $k$ and the second $k$ arguments so we multiply probabilities to get $1/k!^2$.
But yes, it's possible to count the permutations that fulfill the conditions: each way of permuting $2k$ elements such that the first and second $k$ items independently keep their relative order is essentially a way of picking $k$ positions out of the $2k$ possible for the first $k$ items to go - this automatically determines the entire permutation (can you see how?). And the total number of permutations is $(2k)!$ so the probability is $\frac{1}{(2k)!}{2k\choose k}=\frac{1}{k!^2}$. More generally, if you take $n$ items and partition them into parts of size $a_1,a_2,\dots,a_m$ (they don't even have to be contiguous parts), the probability a permutation preserves the relative ordering of each part is $$\frac{1}{n!}{n\choose a_1,\dots,a_{m-1}}=\frac{1}{a_1!a_2!\cdots a_m!}.$$
As you might guess from the form above, the independence argument works for this too.
