How many permutations of $1,2,\cdots, n$ contain exactly $n-2$ digits that are smaller than the digit immediately to their right?
My solution proceeded with recursion. It has some chance of being wrong.
We call all such permutations good permutations. We call a digit good if it is are smaller than the next digit. Let $f(n)$ denote the number of good permutations of $1,2, \cdots ,n$. Note that a good permutation has exactly $n-2$ digits.
Consider any good permutation of $1,2,\cdots ,n+1$. Remove $1$ from the permutation. Note that this can decrease the number of good digits by at most $1$. We have two cases :
$1)$Number of good digits remain the same:
Since the original permutation was good, the new permutation has exactly $(n+1)-2=n-1$ good digits, but has only $n$ digits. But $n+1$ can never be a good digit, since it can never be smaller than any other digit. Hence, after removing $1$, each of $2,3,4, \cdots ,n$ is a good digit. But the only such permutation is $2$ $3$ $\cdots$ $n+1$. Now note that putting back $1$ does not increase or change the number of good digits (unless we put it at the start). Hence, there are exactly $n$ places where $1$ can go.
$2)$Number of good digits decreases:
Since the number of good digits can decrease by at most $1$, in this case, the new permutation has exactly $n-2$ good digits. But there are exactly $f(n)$ of these permutations. When we put back $1$, we cannot place it in any of the following positions because then the number of good digits does not increase:
A) After a good digit itself
B) At the end
There are exactly two places to put $1$ in then. So there are $2f(n)$ permutations in this case.
Combining, we get, $f(n+1)=2f(n)+n$
Is this right?
Thanks in advance
