# 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}$$

-

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.

-