Let A = {1, 2, . . . , n}. For a permutation P = (P(1), P(2), · · · , P(n)) of the elements of A, let P(1) denote the first element of P. Find the number of all such permutations P so that for all i, j ∈ A:
• if i < j < P(1), then j appears before i in P; and
• if P(1) < i < j, then i appears before j in P
My approach is if P(1)=k then for all i<j<k the permutation is in descending order and for k<i<j permutation is in ascending order i.e. for any value of k there is exactly 1 permutation possible.
So, total number of permutations should be n. I wish to be sure if I am correct.
Suppose that $n=8$ and $k=4$. Then $\langle P(2),P(3),\ldots,P(8)\rangle$ must be a permutation of $\{1,2,3,5,6,7,8\}$ in which $3,2$, and $1$ occur in descending order, and $5,6,7$, and $8$ occur in ascending order. However, these two subsequences can be interleaved in many ways. Here are a few:
$$\begin{array}{lcc} 3,2,1,5,6,7,8\\ 3,5,6,2,7,1,8\\ 5,3,6,7,2,8,1\\ 5,6,3,7,2,1,8\\ 5,6,7,8,3,2,1 \end{array}$$
Clearly there is more than one permutation that meets the requirements. However, they aren’t hard to count: once we know which $3$ of the $7$ slots are occupied by $3,2$, and $1$, we know the entire permutation. There are $\binom73=35$ ways to choose those $3$ slots, so there are $35$ permutations of the desired type with $k=4$.
To find all of the permutations of $\{1,2,\ldots,n\}$ of the desired type, just do the same analysis for $k=1,\ldots n$ and sum the results.