A permutation $\left(a_1, a_2, a_3, \cdots , a_n\right)$ of the numbers $(1, 2, 3, \cdots , n)$ is called almost-perfect if there exists exactly one $i \in \{1, 2, 3, \cdots , n-1\}$ such that $a_i > a_{i+1}$. What is the number of almost-perfect permutations of the numbers $(1, 2, 3, … , 11)$?
The problem is from a mock contest. Here is my attempt in solving the problem:
I started by taking small values of $i$ and searched for a pattern. Here $i$ is a number for which $a_i>a_{i+1}$. For $i=1$, the first two numbers will be of the form $(k,1)$ where $k\in \{2,3,\dots,n\}$. Otherwise, there will be more than one pair $(a_i,a_{i+1})$ for which $a_i>a_{i+1}$. So, we have $n-1$ such permutations in this case.
For $i=2$, the first three numbers will be either of the form $(1,k,2)$ or of the form $(2,k,1)$ where $k\in \{3,4,\dots,n\}$. So, we have $2(n-2)$ almost-perfect permutations in this case.
For $i=3$, the first four numbers will be of the form $(1,2,k,3)$ or $(1,3,k,2)$ or $(2,3,k,1)$ where $k\in\{4,5,\dots,n\}$. So, we have $3(n-3)$ almost-perfect permutations in this case.
So, I claim that there are $i(n-i)$ almost-perfect permutations for each $i$. Thus, for $n=11$ we have a total of $1(11-1)+2(11-2)+\dots+10(11-10)=220$ almost-perfect permutations.
I'm not sure whether the above solution is correct or not. But I think this is not the best way to solve the problem. So, I'm looking for a better solution.
Best Answer
We assume $i$ is the term such that $a_i > a_{i+1}$.
Let $A$ be the set of numbers $a_1,\dots,a_i$. Note that $A$ completely determines the permutation, as it must be $a_1<a_2<\dots< a_i$ and then $a_{i+1},\dots,a_{n}$ must be the elements not in $A$ in increasing order.
The only thing that $A$ needs to satisfy is that its size is in the range $[1,n-1]$ and that its largest element is larger than the smallest element not in $A$, in other words we require that $A$ is not one of the $n-1$ intervals of the form $\{1,\dots, i\}$
Hence there are $2^n-2 - (n-1)$ options for $A$.