Probability of increasing order permutation Suppose I have n elements. What's the probability of a permutation such that the first half is increasing and second half can be ordered without any constraints? (A permutation can only have distinct elements)
 A: Let $n=2m$. Whatever choice we make for the set that will occupy the first $m$ places, the probability that these are in increasing order is $\frac{1}{m!}$.
A: Say $n=2k$, for the first half you choose $k$ elements in ${2k \choose k}$ ways, and since we order them in increasing order there is a unique way to arrange them.
Now for the rest of the $k$ elements we have no restriction hence in total we get 
$${2k \choose k}\cdot k!$$
ways.
A: Let $n$ be even.  The number of ways to choose $n/2$ elements from $\{1,\ldots,n\}$ for the first half of the permutation is ${n \choose n/2}$.  Once these elements are chosen, the order in which they appear in the first half of the permutation is uniquely determined because the elements must be in increasing order.  The remaining $n/2$ positions in the permutation can be filled in $(n/2)!$ ways because the elements that will go in the second half of the permutation are already determined and the order in which they appear can be arbitrary.  Thus, the total number of permutations in question is ${ n \choose n/2} (n/2)!$. 
