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


Yes, that is correct. The closed-form solution is $f(n)=2^n-n-1$

  • $\begingroup$ Hmm thanks a lot $\endgroup$ – rah4927 Feb 4 '16 at 16:42

Your solution seems complex. It can be done more simply - My Answer
From my answer it is easy to find general formula.
$$f(n) = \sum_{i = 1}^{n-1}\left\{\binom{n}{i} - 1 \right\} = 2^n-n-1$$
This problem is used in some BdMO Regionals 2015 with $n = 7,8,9$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.