QUESTION: Let $π = π_1π_2......π_n$ be a permutation of the numbers $1,2,3,...,n.$ We say $π$ has its first ascent at position $k < n$ if $π_1 > π_2... > π_k$ and $π_k < π_{k+1}.$ If $π_1 > π_2 > ... > π_{n−1} > π_n$ we say $π$ has its first ascent in position $n.$ For example when $n = 4$ the permutation $2134$ of has its first ascent at position $2$. The number of permutations which have their first ascent at position $k$ is .......
MY APPROACH: This is what I thought. First let us choose $k$ numbers from $n$ numbers. Now, we can arrange those $k$ numbers in a descending order in just $1$ way. Now the remaining $(n-k)$ numbers can be arranged in any way in $(n-k)!$ ways. So total number of ways are- $$\binom{n}k(n-k)!$$
Now, we need to exclude those ways in which the $(k+1)^{th}$ element is less than the $k^{th}$ element (or else the first ascent as defined by the question, does not occur at position $k$). To do this, we need the number of numbers from $(n-k)$ numbers which are greater than the $k^{th}$ number.
Suppose that we have $i$ numbers which are greater than the $k^{th}$ number.. Then we can fill up the $(k+1)^{th}$ place in $i$ ways and the remaining $\big(n-(k+1)\bigl)$ places in $$\bigl(n-k-1\bigl)!\space ways$$ So we can arrive at a concluding answer. But the problem here is, how do I find that $i$, i.e. the number of numbers that are greater than the $k^{th}$ number.
Also, we observe that if we choose $k$ to be the last numbers from $n$ numbers then there is no such $i$ possible. For example, say we have the series $$1,2,3,.....,9$$ and we are asked to pick $k=4$ numbers from here. And if we pick $$6,7,8,9$$ then all the remaining numbers are less than 6 and therefore, it is impossible to have any first ascent at position $k$. Therefore we may conclude that we cannot choose k to be the last numbers from $n$. So we have got another constraint to take care of.
The answer given for this question is- $$\binom{n}k(n-k)!-\binom{n}{k+1}(n-k-1)!$$
How is this possible to do?
Any help or suggestion or some other smarter way to think about this sum will be much appreciated.
Thank you so much.
You were doing fine. You missed the following:
So you fix the first $k$ and there are $\binom{n}{k}$ ways to do this but then you do not know what happens to the next one. The deal is that you just have two possibilities, either $\pi _k<\pi _{k+1}$ or the opposite $\pi _k>\pi _{k+1}$ Notice that if the latter happens(This is exactly what you dont want) then you will have the chain $\pi _1>\cdots >\pi _k>\pi _{k+1}$ without paying any attention of what happens next.
By your analysis, this can be done in $$\binom{n}{k+1}(n-(k+1))!$$ and so from the whole possibilities, that you computed, you want to take the above scenario out, ending in the formula $$\binom{n}{k}(n-k)!-\binom{n}{k+1}(n-k-1)!$$