0

We call a permutation $\sigma$ of $\{1,2,...,n\}$ a semi-ordered permutation if $\sigma_1 > \sigma_2 > ... > \sigma_{k-1} > \sigma_k < \sigma_{k+1} < ... < \sigma_{n-1} < \sigma_{n}$ where $\sigma_i$ is the number placed at position $i$ of the permutation.

I need to count the number of such permutations. Due to the definition, I know that $\sigma_k$ must be $1$ since it is the only number that is smaller than all other numbers in the range $[1,n]$.

However, the choices seem to be dependent. It appears that where I have put the number $n$ affects where I can put the number $n-1$, etc. How do we go about counting these?

TheNotMe
  • 4,841

1 Answers1

2

As you correctly said $\sigma_k=1$. Now for $\sigma_k$ there are $k-1$ numbers to its left and $n-k$ numbers to its right. Thus for any $k$ number of possible permutations are $n-1 \choose {k-1}$ which chooses $k-1$ numbers to its left and as there is only one possible configuration for those numbers this will be your permutations for any particular $k$.

Therefor total number of configurations are $$\sum_{1}^{n} {n-1 \choose {k-1}}=2^{n-1}$$ This expression comes from binomial expansion

avz2611
  • 3,658
  • If you intend to exclude the possibility that $1$ is in the first or last positions, your summation should start with $k = 2$. – N. F. Taussig Nov 16 '17 at 13:09
  • No, i didn't exclude them thus my series is starting from $k=1$. Does my answer imply that? – avz2611 Nov 16 '17 at 13:11
  • In that case, the upper index of your summation should be $n$. Otherwise, you are excluding the possibility that there is a $1$ in the last position since $(n - 1) - 1 = n - 2$. – N. F. Taussig Nov 16 '17 at 13:13
  • Yes you are right my limits should be from $1$ to $n$ corrections made – avz2611 Nov 16 '17 at 13:14
  • A note about grammar: It's is a contraction for it is. Its is the possessive form of it. You meant the latter. – N. F. Taussig Nov 16 '17 at 13:14