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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.