Hm, well in the 3-case the ({1,2,3}) and ({3,2,1}) cases are equivalent, each with probability (\frac{1}{2^2}). There are 4 permutations left, each of which is a single exchange of adjacent elements away from one of the strictly increasing / decreasing cases, and each of which evidently has...