Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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